Bead sort: faster than O(N log N) sort

There are "sorting algorithms" faster than O(n log n); that limitation only applies to comparison sorts. These typically have complexity depending on the keyspace (for example, counting-sort has linear complexity in whichever is greater, the size of the input list or the keyspace).<p>They're also typically kind of useless, as in this example, because we rarely care to sort an arbitrary list of integers with no metadata. Radix-sort is a rare exception, in that it can easily be modified to carry metadata, hence people actually using it in some applications.

<a href="http://en.wikipedia.org/wiki/Radix_sort" rel="nofollow">http://en.wikipedia.org/wiki/Radix_sort</a>

Previously posted here <a href="http://news.ycombinator.com/item?id=257374" rel="nofollow">http://news.ycombinator.com/item?id=257374</a>

Is there any theory on analyzing sorting real world objects? Like playing cards.<p>In a computer, picking the n'th item in an array is O(1), in the physical world it's O(n). In a computer inserting an item is O(n), but in the physical world it's O(1).<p>Are there any good algorithms for sorting playing cards?

I thought about this sort on my own a couple years ago, and I thought I'd discovered the most amazing thing in sorting :P<p>Not only did I realize I was beaten to the punch few years earlier, but also that efficiency is lost in implementation.

The brightly coloured slides on CSP-style programming, using Occam, at <a href="http://www.cs.kent.ac.uk/teaching/08/modules/CO/6/31/slides/" rel="nofollow">http://www.cs.kent.ac.uk/teaching/08/modules/CO/6/31/slides/</a> include a O(n) "sort pump" starting on page 14 of <a href="http://www.cs.kent.ac.uk/teaching/08/modules/CO/6/31/slides/replicators.pdf" rel="nofollow">http://www.cs.kent.ac.uk/teaching/08/modules/CO/6/31/slides/...</a> that's also O(n) for space.<p>Those slides are an interesting read generally if you're not familiar with CSP/Alef/Limbo-style programming, despite the crufty Occam syntax.

If you have to represent each value in unary, how can you even set up the input and read the results in less than O(N^2), much less carry out the "fall"?

<a href="http://en.wikipedia.org/wiki/Spaghetti_sort" rel="nofollow">http://en.wikipedia.org/wiki/Spaghetti_sort</a><p>The advantages of this sort:<p>1) It involves something ridiculous (in the CS context) like Pasta.<p>2) You have an excuse to play the theme from "The Good, The Bad, and The Ugly" in that section of the talk.

Now we will need extra hardware just to do sorting!