Gnome Sort
See a single pointer walk forward while neighbours are in order, and step back swapping whenever they aren't.
How it works
Gnome sort works like a garden gnome sorting a line of flower pots. It looks at the pot in front of it and the one just before it. If they are in order, it steps forward. If not, it swaps them and steps back, then checks again. When it walks off the end of the line, everything is sorted.
It needs only one loop and one position, with no nested loops. Stepping back after a swap carries a small value left until it meets a smaller neighbour, which is the same work insertion sort does, but done with swaps instead of shifts.
When to use it
Gnome sort is mostly a teaching example: it shows how a sort can be built from a single loop. It is fast on nearly sorted arrays, but insertion sort does the same job with fewer writes.
Complexity
It is stable: it only swaps neighbours that are strictly out of order, so equal values never pass each other.
| Case | Time | When |
|---|---|---|
| Best | O(n) | Already sorted: it walks straight to the end |
| Average | O(n²) | Random order |
| Worst | O(n²) | Sorted in reverse: every value walks to the front |
| Extra space | Why |
|---|---|
| O(1) | It swaps neighbours in place, using a single position variable |
Implementations
function gnomeSort(array) {
let i = 0;
while (i < array.length) {
if (i === 0 || array[i - 1] <= array[i]) {
i++;
} else {
[array[i - 1], array[i]] = [array[i], array[i - 1]];
i--;
}
}
return array;
}
def gnome_sort(array):
a = list(array)
i = 0
while i < len(a):
if i == 0 or a[i - 1] <= a[i]:
i += 1
else:
a[i - 1], a[i] = a[i], a[i - 1]
i -= 1
return a
#include <utility>
#include <vector>
std::vector<int> gnomeSort(std::vector<int> a) {
const int n = static_cast<int>(a.size());
int i = 0;
while (i < n) {
if (i == 0 || a[i - 1] <= a[i]) {
i++;
} else {
std::swap(a[i - 1], a[i]);
i--;
}
}
return a;
}