Home/Sorting/Gnome sort
Search algorithmsCTRL K

Gnome sort

· one pointer, forward and back
/sorting/gnome-sort
COMPARISONS
0
so far
SWAPS
0
one per inversion fixed
POINTER
0
where the gnome stands
STEPS BACK
0
after a swap
SORTED PREFIX
0
everything left of the pointer
comparingswappedin place
n = 24 · seed 7 · 753 steps
step 0 / 752
Size24
gnome_sort.ts
1
function gnomeSort(array: number[]) {
2
  let index = 0;
3
  while (index < array.length) {
4
    if (index === 0 || array[index - 1] <= array[index]) {
5
      index++;
6
    } else {
7
      swap(array, index - 1, index);
8
      index--;
9
    }
10
  }
11
}
CURRENT STEP
line 2

Start at index 0. The gnome keeps everything left of it sorted.

// how it works

Understanding Gnome sort

gnome sort · the garden gnome lining up flower pots
01

The idea

Gnome sort has one pointer and one rule. If the element under the pointer is not smaller than the one before it, step forward; otherwise swap the two and step back. Everything to the left of the pointer is always sorted, so when the pointer walks off the end the array is done.

It is insertion sort written without a nested loop: the stepping back is the inner loop, done with swaps instead of shifts. Same comparisons, more writes, and a listing short enough to remember.

02

The four stages

1
comparethe pointer with its left neighbour
2
step forwardin order: the prefix grew
3
swapout of order: exchange them
4
step backcheck the pair before
03

Complexity

best
O(n)already sorted: n − 1 comparisons
average
O(n²)like insertion sort
worst
O(n²)reversed input
space
O(1)one pointer
04

Versus its siblings

COMPARISONS AT N = 1 000 · RANDOM INPUT
bubble
499,500
gnome
250,000
insertion
250,000
quick
13,900
merge
8,700
gnome does insertion's comparisons with three times the writes
05

Pseudocode

GNOMESORT(array)
  index ← 0
  while index < n
    if index = 0 or array[index − 1] ≤ array[index]: index ← index + 1
    else: swap array[index − 1], array[index]; index ← index − 1
06

When to use

When the code must be tiny: embedded scripts, interview whiteboards, a shell one-liner.
Nearly sorted input, where it runs in almost linear time.
07

Pitfalls

Every step back is a swap of two writes; insertion sort's shift is one.
The optimised version remembers where it was before stepping back, and jumps straight there.
It is not stable if the comparison is strict in the wrong direction; keep the ≤.
08

History

Hamid Sarbazi-Azad described it in 2000 as stupid sort; Dick Grune renamed it gnome sort after the Dutch garden gnome who sorts flower pots by looking at the pot next to him. It is the simplest correct sorting loop that can be written.

Back to Sorting