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.
O(n) sorting algorithms are only impractical if the size of the keyspace dwarfs the number of elements to be sorted. In general a key is a variable-length string of bits, which makes for an exponentially-sized keyspace, so you want to stick with comparisons of element pairs.
But "metadata" has nothing to do with it. The last bead in each BeadSort row can contain a sticker with some metadata. That kind of trick generalizes to all sorts.
Wrong. The beads in columns remain in the original order (not sorted) and so would these stickers.
Perhaps you can make it smaller than log(n) for many use cases by restricting the type of input you accept but O(f(x)) only refers to the worse case.
Lets say you have restricted w to 32. Then you also know that n <= 2^32. If you now for instance are using mergesort then you also know that the number of recursions are at most 32 (since you split the input in half each time), i.e. it executes within at most 32n operations. So with that logic mergesort would also be linear.
In the above case M = 32, f = mergesort and g(x) = x because no matter of large input you have mergesort will always take less than or equal to 32n operations (since log(n)<=32) .
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).
Are there any good algorithms for sorting playing cards?
Not only did I realize I was beaten to the punch few years earlier, but also that efficiency is lost in implementation.
Those slides are an interesting read generally if you're not familiar with CSP/Alef/Limbo-style programming, despite the crufty Occam syntax.
The advantages of this sort:
1) It involves something ridiculous (in the CS context) like Pasta.
2) You have an excuse to play the theme from "The Good, The Bad, and The Ugly" in that section of the talk.