Combsort for Softsim

Chuck Moore has put a bubblesort script on one of his colorForth pages:

bubble nt a! for @+ @ - + - -if
@ a -1 + a! @ push !+ pop ! then drop next ;

Simple and compact. I was interested to see if such a simple sort could be speeded up without using too many more instructions. I found the Wikipedia entry for Combsort which calculates a decreasing gap between the two comparison values with the aim of getting the smallest values moved into place as quickly as possible.

So I started transliterating the Wiki algorithm into colorForth. The gap is shrunk by a factor of 1.3 which is apparently a result of some extensive testing with varying shrink factors. Initially I wrote a subroutine to multiply by 10 then divide by 13 (plus lots of shuffling registers around):
shrinkgap a push dup dup or over
   10 * -13 --u/mod pop a! push
   drop drop drop pop ;

And then it hit me that 1.3 is only an approximation. There's nothing absolute about it. It occurred to me that if would be much more efficient to use factors of 2 where possible. So my shrink calculator is simply:

2/ dup 2/ +

In other words take (1/2+1/4) (i.e. 0.75) of the gap. 1/1.3 = 0.77 which is amazingly close to 0.75.

In the end my Combsort still took lots of code and only saved a few hundred cycles compared to Chuck's bubblesort.

comb sort,
504 node 0 org,
4 , 19 , 7 , 1 , 12 , 13 , 0 ,,
11 , 3 , 9 ,,17 , 16 , 13 , 6 ,,
2 , 1ffff , 5 ,,
shrink 11 2/ dup 2/ + if ;
   then - 2* - ;
comb tn push dup dup,
...begin,
......16 pop dup push a!,
......dup or swpd push,
......shrink,
......over over - . +,
......for dup a + b!,
......@ - 1 + @b + -if,
......gt 20 @ @b ! !b pop pop,
......dup or - push push,
......le then drop @+ drop next,
...26 dup dup dup or - +,
......if dup or - then gap1?,
......pop swpd?,
......over - and or -,
...until pop ;,
2e 17 0 comb 32 r---