gnome sort

Gnome sort is a compact O(n²) algorithm to re-arrange a sequence of elements into order. In his article on Gnome sort, Dick Grune describes the algorithm as follows:

Gnome Sort is based on the technique used by the standard Dutch Garden Gnome (Du.: tuinkabouter). Here is how a garden gnome sorts a line of flower pots. Basically, he looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise he swaps them and steps one pot backwards. Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.

The Gnome sort article on Wikipedia describes a slightly modified algorithm.

Implementation in Redcode:

          org    inner

          temp   equ (outer-1)

outer     mov    }p,             temp
p         mov    FIRST+LENGTH-1, {p
          nop    >y,             }p
          mov    temp,           }p
          sne    y,              #LENGTH
          nop    <y,             {p
inner     slt    *p,             {p
y         djn    inner,          #LENGTH-1
          jmn    outer,          y

The redcode implementation is just 9 lines long, and requires 4.5n²-3.5n cycles to sort the sequence in the worse case.