Sorting Algorithm

Gnome Sort

“The Indecisive Gardener”

Time: O(n²)

Space: O(1)

History

Originally called "Stupid Sort" (no, really) by Hamid Sarbazi-Azad in 2000, it was rebranded as Gnome Sort by Dick Grune. The metaphor is a garden gnome sorting flower pots. He looks at two pots. If they are out of order, he swaps them and steps back. If they are fine, he steps forward.

It is essentially Insertion Sort implemented by someone who hates nested loops.

How It Works

Gnome Sort uses a single index variable. It's a state machine with just two rules: move forward if things look good, move backward if you made a swap.

The Algorithm Step-by-Step

Start: At index 0.
Check: Compare current pot with previous pot.
Good?: If they are in order (or we are at start), step forward.
Bad?: If they are out of order, swap them and step backward.
Repeat: Until you reach the end.

Connection to Insertion Sort

It produces the exact same sequence of swaps as Insertion Sort, but instead of an inner loop, it physically moves the "cursor" back and forth.

Best CaseO(n)

If sorted, the gnome just walks from start to finish without stopping.

Worst CaseO(n²)

The gnome spends most of his life walking backwards. It's painfully slow.

Average CaseO(n²)

Same as Insertion Sort, but usually slightly slower due to the overhead of variable updates.

SpaceO(1)

In-place. Only needs one index tracker.

Code Walkthrough

Real implementations in multiple programming languages. Select a language to view idiomatic code.

1def gnome_sort(arr: list[int]) -> None:
2    """Sort array in-place using gnome sort."""
3    n = len(arr)
4    i = 0
5
6    while i < n:
7        if i == 0:
8            i += 1
9        elif arr[i] >= arr[i - 1]:
10            # In order - move forward
11            i += 1
12        else:
13            # Out of order - swap and move backward
14            arr[i], arr[i - 1] = arr[i - 1], arr[i]
15            i -= 1