Comb sort

Comb sort (also known as Dobosiewicz sort) makes a number of passes through a sequence of elements, exchanging any elements which are out of order. With each pass the distance between compared elements decreases. The algorithm terminates when all elements are in order.

In the redcode implementation, the value of the temp element is used as a flag to determine whether or not any exchanges occurred in the last pass.

Implementation in Redcode:

          ra     equ 4
          rb     equ 5

          org    inner

          temp   equ (outer-1)

outer     mov    #LENGTH,        y
          sub.b  gap,            y
          mov.f  q,              p
          sub.b  gap,            p
          sub    temp,           temp

inner     slt    {p,             <p
y         djn    inner,          #LENGTH-(LENGTH*ra/rb)
          jmz    done,           y

          mov    @p,             temp
p         mov    FIRST+LENGTH,   FIRST+LENGTH-(LENGTH*ra/rb)
          mov    temp,           *p
          djn    inner,          y

done      mul    #ra,            gap
gap       div    #rb,            #(LENGTH*ra/rb)

          jmn    outer,          gap
          nop    >gap,           {outer
          jmn    outer,          temp

q         dat    FIRST+LENGTH-p, FIRST+LENGTH-p