Gnome Sort - The Simplest Sort Algorithm

Dick Grune

The simplest sort algorithm is not Bubble Sort..., it is not Insertion Sort..., it's Gnome Sort!

Gnome Sort is based on the technique used by the standard Dutch Garden Gnome (Du.: tuinkabouter). Here is how a garden gnome sorts a line of flower pots. Basically, he looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise he swaps them and steps one pot backwards. Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.

void gnomesort(int n, int ar[]) {
	int i = 0;

	while (i < n) {
		if (i == 0 || ar[i-1] ≤ ar[i]) i++;
		else {int tmp = ar[i]; ar[i] = ar[i-1]; ar[--i] = tmp;}
	}
}

Download the code (zipped) here.

The same algorithm was described earlier by Hamid Sarbazi-Azad in Hamid Sarbazi-Azad, Stupid Sort: A new sorting algorithm, Department of Computing Science Newsletter, University of Glasgow, 599:4, 2 October 2000.

---

[Home Page]

---

... and my name is not Richard ...