Gnome Sort

What is gnome sort?

Gnome sort uses one loop and one pointer. Picture a garden gnome sorting flower pots in a row. It looks at the pot in front of it and the one just behind. If they are in order, it steps forward. If not, it swaps them and steps back. When it walks off the end of the row, the pots are sorted.

It was first called “stupid sort”, and it is about as simple as a sorting algorithm gets. There are no nested loops in the code at all, just a pointer moving forward and back.

How it works, step by step

Press play above. Blue bars are being compared, orange bars are being swapped. Follow the pair as it moves: forward while things are in order, backward while it is carrying a small value home.

1. Start with the pointer p at 0.
2. If p is 0, or the value on the left is smaller or equal (a[p - 1] <= a[p]), step forward: p += 1.
3. Otherwise, swap a[p - 1] and a[p], then step back: p -= 1.
4. Repeat until p reaches the end of the list.

Look closely and you will see insertion sort. Each time the gnome steps back, it is carrying a value left until it fits, exactly like insertion sort. The difference is that afterwards the gnome walks forward again, one step at a time, instead of jumping ahead. Those extra steps are comparisons insertion sort skips.

Time and space complexity

Best case, O(n): the list is already sorted. The gnome walks straight to the end, making n − 1 comparisons and no swaps.

Worst case, O(n²): the list is reversed. Every new value has to be carried back to the front one swap at a time, and then the gnome has to walk forward again. That is about n²/2 swaps plus the walk back.

Average case, O(n²): on a shuffled list each value is carried back about halfway.

The number of swaps is exactly the same as insertion sort makes, one per out-of-order pair. Gnome sort just adds extra comparisons on the walk forward.

Space is O(1). One pointer, and swaps in place.

Common mistakes

• Forgetting the p == 0 check. At the front there is no left neighbor, so comparing a[p - 1] would read the wrong value. The check must come first.
• Using < instead of <= in the forward test. With equal neighbors the gnome would swap them back and forth forever.
• Stepping back without swapping, or swapping without stepping back. Both break the loop.

One known improvement: remember where you were before stepping back, and jump straight there once the value is placed. That skips the walk forward and turns gnome sort into insertion sort.

When to use it

Almost never for real work. Insertion sort does the same swaps with fewer comparisons, and built-in sorts are much faster on anything but tiny lists.

Gnome sort is still great for learning:

• It shows that a sort does not need nested loops. One loop with a pointer that moves both ways is enough.
• It makes the link between swaps and out-of-order pairs easy to see.
• It is a good warm-up for proving a loop ends: every step forward or swap makes progress, so the gnome can’t walk forever.

Questions

Is gnome sort stable?

Yes. It only swaps neighbors when the left one is strictly bigger, so equal values keep their order.

How is gnome sort different from insertion sort?

They make the same swaps. Insertion sort jumps ahead after placing a value; gnome sort walks forward one step at a time, which costs extra comparisons.

Why is it called gnome sort?

It was described as a garden gnome sorting a line of flower pots, one step forward or back at a time.