Gnome Sort

Steps forward while ordered; on an inversion it swaps and steps back, then resumes — insertion sort expressed with a single moving index.

Category

Sorting

Time complexity

O(n²)

Space complexity

O(1)

Pseudocode

i ← 0
if a[i] ≥ a[i−1]: step forward
else: swap and step back
done at end of array

Reference implementation

i = 0
while i < n:
    if i == 0 or a[i] >= a[i-1]:
        i += 1
    else:
        a[i], a[i-1] = a[i-1], a[i]; i -= 1

Open the interactive Gnome Sort visualisation →