2 ms·
"And do we have any idea what God's Number is for sorting a deck of cards?" It depends on your definition of sorting. Since we have a known, finite, compact se
by jerf 8y ago
"And do we have any idea what God's Number is for sorting a deck of cards?"
It depends on your definition of sorting. Since we have a known, finite, compact set of incoming inputs, essentially the numbers 1-52, as rocqua says we can use a bin sort with 52 bins and sort the cards in essentially 52 operations. This is physically practical as well. Generally the "constant overhead" on it is such that people will sort with something more like a merge sort, but it's certainly completely practical to find a space large enough to hold the entire deck laid out physically.
If you limit sorting to the computer science sense of the term, in which the sort must be accomplished by swaps, I expect it could be worked out pretty easily by people skilled in the art of sorting, again because the small constant size and input makes it relatively easy. I know it can be proved that this style of sort can't take less than O(n log n) comparisons, but I'm not 100% sure I can guarantee it's literally ciel(52 * log2 52). Somebody else may be able to.