Shellsort routine - 2 -

another SHELL-Sortroutine 
Captured from a message from Ian Collier (see EMail Addresses) in a public 
Internet news group (see Internet - Newsgroups) 

"That algorithm is a weird variation on Shell sort that I've never seen 
before.  A shell sort is a bit like a glorified bubble sort but it usually 
performs better, and it can be written as follows.  Notice that the last 
pass, with d=1, is equivalent to a bubble sort; we expect the list to be 
mostly in order by this time so that the bubble sort finishes quicky.  The 
earlier passes are like bubble sorts that make elements travel more 
quickly when they are further out of place.  [A quick test on 300 lines of 
news articles showed that the above program performed 10428 comparisons. 
 A bubble sort did 33374 comparisons.]"   

 
/* ------------------------------------------------------------------ */
/* function: variation of Shell sort                                  */
/*                                                                    */
/* call:     ShellSort                                                */
/*                                                                    */
/* returns:  nothing                                                  */
/*                                                                    */
/* notes:    You must save the elements to sort in the stem "STEM."   */
/*           stem.0 must contain the number of elements in the stem.  */
/*                                                                    */
ShellSort: PROCEDURE expose stem.
  d = stem.0 % 2                /* d is a distance measurement        */
  do while d > 0
     do until finished          /* start of mini-bubblesort loop      */
        finished = 1
        do i=1 to stem.0-d
           j = i+d      /* we now compare and swap items i and i+d    */
           if stem.i >> stem.j then do                       /* v2.80 */
              temp = stem.i
              stem.i = stem.j
              stem.j = temp
              finished = 0
           end
        end i
     end                        /* end of mini-bubblesort loop        */
     d = d%2
  end
RETURN