Extraordinary claims. Ordinary investigations.

Maggie Sort Algorithm

It’s one of the classic computer science problems. How to sort a list of elements? The old, simple pleasure of sorting music records in alphabetical order is now a matter of clicking a tab and waiting some fractions of a second. Doing that in the smallest possible fraction of a second, finding the optimal sorting algorithm, is however what makes this classic problem a subject explored to this day.

Or, as Eric Schmidt from Google asked Barack Obama, “what is the most efficient way to sort a million 32-bit integers?

Surprisingly, Obama answers “I think the bubble sort would be the wrong way to go”. Surprising because that’s a quite good retort, as the bubble sort algorithm, for all the simplicity with which it can be implemented and understood, is also one of the most inefficient. It’s not recommended for lists larger than a dozen elements, and definitely not for a million. Whether it was a staged joke or not, fact is we have the first nerd President of the modern age.

As it turns out, 19-month-old Maggie sort algorithm is not only much more efficient than bubble sort, it’s a very good algorithm on its own. As fellow Girino pointed out, the little girl uses some convenient characteristics of the objects to sort them: she starts right from the smallest one, and constantly checks if two of them fit together to see if their position is correct or not. “I would say it’s a variation of the Pigeonhole sort, with some randomness.”

Girino even plotted Maggie Sort versus Quicksort and Python’s internal sort:

subquadraticb

Here is Maggie sort versus Python’s sort in more detail:

subquadratic2b

It’s much more efficient exactly because it deals with a list of elements with special characteristics. Little Maggie sorted these things out.

I tried to plot her cuteness versus bubble and quick sort, but it was cute overload. [via Kenjiria, with many thanks to Girino]

Blog Widget by LinkWithin

Popularity: 2% [?]

Posted in Miscelaneous,Science | 2 comments

2 Comments so far

  1. Maggie's Dad June 28th, 2009 3:32 pm

    Best writeup I’ve seen so far. Thanks!

  2. Mori July 7th, 2009 6:10 am

    Wow, great to read that from Maggie’s Dad :)

Leave a reply

Live Comment Preview