Gnome sort
Gnome sort keeps one position and repeatedly compares the value there with the value immediately before it. If they are in order, or the position is at the start of the array, it steps forward. If they are out of order, it swaps them and steps back one position to check again. There is no remembered key value and no separate inner loop — insertion sort's shifting is replaced by a sequence of single swaps and backward steps that has exactly the same net effect.
When it is the right choice
Gnome sort is not a serious choice for real work: it performs the same O(n²) comparisons and writes as bubble sort or insertion sort, with no offsetting advantage. Its value is entirely pedagogical — it is the shortest correct sorting algorithm to write and to trace by hand, useful for building intuition about what a sort has to guarantee before reaching for a faster one.
How it works
- Start at the first position.
- If the position is at the start of the array, step forward one position.
- Otherwise, compare the value at the current position with the value immediately before it.
- If the value here is smaller, swap the two values and step back one position.
- If it is not smaller, step forward one position instead.
- Once the position reaches the end of the array, every value has been checked against its neighbour and the array is sorted.
Worth noticing
- Its single index quietly does the job of insertion sort's two nested loops: stepping back after a swap re-checks the newly-moved value against its new neighbour, which is exactly what insertion sort's shifting loop does one comparison at a time.
- It performs a comparison and, often, a swap for every step, including backward steps — on reversed input this revisits the same positions repeatedly, giving the same O(n²) worst case as bubble sort.
- It is stable: a value only ever swaps past a strictly smaller value, so equal values keep their original relative order.
Cost
- Best
- O(n)
- Average
- O(n²)
- Worst
- O(n²)
- Extra space
- O(1)
- Stable
- Yes