4 ms·
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.)
by lotharbot 14y ago
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.)
- pbiggar 14y agoWith 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.