2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.