Gnome Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Gnome Sort

The garden gnome sort: a remarkably simple single-loop exchange sort modeled after a gnome checking adjacent flowerpots and moving backward or forward accordingly.

How it works

Gnome Sort (originally named "Stupid Sort" by Hamid Sarbazi-Azad in 2000, and later renamed by Dick Grune) is conceptually identical to Insertion Sort, but is implemented using only a single loop index. The namesake analogy describes a garden gnome sorting a line of flowerpots:

1. Examine pots: The gnome starts at the first pot (\(i = 0\)). He looks at the current pot and the one before it.
2. Step Forward: If they are in the correct order (or if the gnome is at the starting pot), he takes one step forward: \(i \leftarrow i + 1\).
3. Swap and Step Backward: If the pots are in the wrong order, he swaps them and takes one step backward: \(i \leftarrow i - 1\).
4. Termination: The gnome continues walking back and forth until he reaches the end of the line, guaranteeing the pots are fully sorted.

Complexity

Interactive visualization

Pseudocode

procedure gnomeSort(A):
  n ← length(A)
  i ← 0
  while i < n:
    if i == 0 or A[i] ≥ A[i - 1]:
      i ← i + 1
    else:
      swap A[i], A[i - 1]
      i ← i - 1

JavaScript implementation

function gnomeSort(arr) {
  const n = arr.length;
  let i = 0;
  while (i < n) {
    if (i === 0 || arr[i] >= arr[i - 1]) {
      i++;
    } else {
      [arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
      i--;
    }
  }
  return arr;
}

Pros and cons

When (not) to use it

• Teaching logic: Excellent for illustrating how nested control loops can be converted into single index traversals.
• Practical sorting tasks: Do not use Gnome Sort for real-world workloads. Insertion Sort is always slightly faster, and Quicksort is orders of magnitude faster.