[Solved]: Radix sort and changing bases

Problem Detail: 

I have recently learned about radix sort. I am aware that you can change the base of the numbers you need to sort but I don't really understand why this is good for the radix sort. Radix sort runtime is $O(d(n+k))$ where $d$ is the number of digits in the numbers, and $k$ is the base. So shouldn't there be a permanent ratio between $d$ and $k$ so that the runtime is optimized? How should I choose the base in any other way?

Asked By : Yinon Eliraz

Answered By : Kyle Jones

The asymptotic runtime ignores access times for the digits. On typical hardware a base 256 number can be manipulated faster than extracting base 10 digits from the same number.

If you have multiple CPUs, you can more easily exploit parallel processing by using a larger base. The large base will spread the numbers across many buckets which can then be sorted in parallel.

Another reason to change bases is if you know your data has a bias (such as Benford's Law) that would cause the numbers to initially cluster into only a few buckets.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44138

3.2K people like this

 Download Related Notes/Documents