Re:How to pair socks from a pile efficiently?
by chris_wot on Saturday January 19, 2013 @11:04PM
(#5085964)
I've been thinking about this algorithm. If you had millions of items, then wouldn't the process of dividing into buckets, and then sorting these buckets which are massive take a long time? Unless of course you recursively sort each bucket into sub-buckets...
[ Parent
| on HN ]
Re:How to pair socks from a pile efficiently?
by lotharbot on Saturday January 19, 2013 @11:28PM
(#5086003)
It's typical to recurse until you're down to small enough sets to easily sort using some other algorithm (usually insertion sort on groups < 10 elements.)
Re:How to pair socks from a pile efficiently?
by pbiggar on Saturday January 19, 2013 @11:45PM
(#5086031)
With radixsort, you don't even need to. By the time you get to the deepest bucket, all the entries have an identical prefix and unique suffix. So they can all be sorted in O(N).
You could construct situations where it would be faster to switch to insertion sort (maybe radix of 2, stop 3 recursions from the end), but in practice you'd pick a radix better (with a radix of 8, you could do the entire thing in 4 recursions and the final recursion over 64 items is faster than insertion sort of 64 items, probably).
Note that you'd generally use LSB radixsort over MSB radixsort, so you'd have a set number of passes over the array, and no recursion.
Re:How to pair socks from a pile efficiently?
by pbiggar on Saturday January 19, 2013 @11:39PM
(#5086025)
You recursively sort each bucket into subbuckets, and there is a known recursion limit (3 in this case).
Here's code for an LSB radix sort, which doesn't recurse, but is the same idea: https://github.com/pbiggar/sorting-branches-caching/blob/mas...