Gnome sort

O(n²)

Gnome sort uses a single index: if the current pair is in order it steps forward, otherwise it swaps them and steps back. It is essentially insertion sort done with swaps and no nested loop — simple to state, O(n²), and mostly of pedagogical interest.

Array
Edit the input and press Play

How it works

  1. Look at the current element and the one before it.
  2. If they are in order (or you are at the start), step one position forward.
  3. If not, swap them and step one position back.
  4. Repeat until the index walks off the end.

Pseudocode

1gnomeSort(a):                       # O(n²)2  i ← 03  while i < n:4    if i = 0 or a[i-1] ≤ a[i]:5      i ← i + 1                       # step forward6    else:7      swap(a[i-1], a[i]); i ← i - 1   # swap and step back