Gnome Sort

While search the NIST Algorithms Dictionary for a simple sort algorithm that would be easy to write in CUSP asm, I came across gnome sort, which I’d never seen before.

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.

Awesome! The implementation is 23 instructions in CUSP asm for an arbitrary segment of continous memory.

---