Log in

No account? Create an account

Gnome Sort

Even though I have  taught an algorithms class many times, I only learned about the gnome sort a couple of days ago. I discovered it in a video of "audiblizations" of various sorting algorithms, which I include below:


Gnome sort is the last one, starting at 1:12.  I did a little googling and found its wikipedia page.  There's nothing special about it from an efficiency point of view. It has a worst case time of O(n2), although like insertion sort it has a best cast time of O(n) when the array is already sorted.

It's still impressive. What it lacks in efficiency it makes up for in simplicity and elegance. It is the only sort  algorithm I've ever seen that does not require a nested loop. Here's a  C implementation from Dick Grune's website that's only 4 lines long:

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;}

 According to the wikipedia page, (and most other pages I have looked at), the name comes because it behaves like a dutch garden gnome sorting flower pots. Until I discovered this algorithm, I didn't know dutch garden gnomes did that. Or that there was even any significant difference between dutch garden gnomes and garden gnomes of other nationalities.

I googled the phrase dutch garden gnome to learn more about this quaint bit of folklore. Most of the hits I got were about the gnome sort, and the ones that weren't didn't go into their behavior with flower pots. I suspect the creators just thought "gnome sort" was a cool name and then made up the flower pot thing to justify it. A lot like the way acronyms sometimes come before their expansions in computer terms such as kermit and lisa.