Gnome Sort

The Garden Gnome’s Sorting Rule

Proposed by Hamid Sarbazi-Azad (originally nicknamed Stupid Sort and popularized by Dick Grune as Gnome Sort), the algorithm models how a garden gnome arranges flower pots along a path without remembering where he came from:

• Look at the pot right in front of you (pos) and the pot one step behind you (pos - 1).
• In order (pos == 0 or a[pos] >= a[pos - 1])? Take one step forward (pos += 1).
• Out of order (a[pos] < a[pos - 1])? Swap the two pots and take one step backward (pos -= 1) to check the swapped pot against its new left neighbor!
• Once pos == len(a), the entire row is sorted.

Why One while Loop Terminates in O(n + inversions)

At first glance, stepping pos backward looks dangerous — could the cursor bounce back and forth forever?

Track the potential via inversions:

1. Every backward step (pos -= 1) swaps an inverted pair (a[pos - 1] > a[pos]), strictly decreasing the total inversion count I by 1. Since an n-element array has at most n(n - 1) / 2 inversions, at most I backward steps can ever occur across the entire run!
2. Because pos starts at 0, ends at n, and drops by 1 at most I times, the number of forward steps (pos += 1) is exactly n + I.

Total loop iterations equal n + 2I — linear O(n) when already sorted (I = 0) and O(n²) on reversed input!

Clean Python Implementation

We can even add a tiny teleportation bookmark (next_pos) so that after shuttling an element leftward into place, the gnome jumps straight back to the frontier instead of re-checking already-ordered pairs on the walk forward:

def gnome_sort(nums: list[int]) -> list[int]:
    """Classic single-loop Gnome Sort: O(n + inversions) time, O(1) space, stable."""
    pos = 0
    n = len(nums)
    while pos < n:
        if pos == 0 or nums[pos] >= nums[pos - 1]:
            pos += 1
        else:
            nums[pos], nums[pos - 1] = nums[pos - 1], nums[pos]
            pos -= 1
    return nums