Radix sort and changing base

Question

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 ration between $d$ and $k$ so that the runtime be optimized?

How should I choose the base in any other way?

Answer 1

An observation I think you're missing is that the number of digits in each number depends on the base. For example, the number 255 requires three digits in base 10 (decimal), 8 digits in base 2 (binary), two digits in base 16 (hexadecimal), and 1 digit in base 256 (I don't think there's a name for it). More generally, the number n requires Θ(log_b n) bits when written out in base b. Normally, big-O notation ignores the bases of logarithms, but since b is a variable here, we need to take it into account. Using the change-of-basis formula for logarithms, we get that we need Θ(log n / log b) bits to write out a number n.

As a result, let's suppose that you're sorting a list of n numbers, where the maximum number you're sorting is the number U. If you pick a base b, then there will be Θ(log_b U) = Θ(log U / log b) base-b digits in the largest number, so you'll need Θ(log U / log b) rounds of radix sort. Each round requires time Θ(n + b), so the total runtime will be Θ((log U / log b)(n + b)).

This is an interesting runtime because depending on the relative values of n, U, and b, you get different results. For example, suppose you pick b to be any constant value. Then this runtime is Θ(n log U), which is pretty fast, but the constant factor hidden here makes quite a lot of a difference. If you use base n, where n is the number of elements, then asymptotically the runtime is Θ(n log U / log n), which is asymptotically faster than any fixed base but typically a bit slower in practice except for colossal inputs. If you know that U is going to be much, much smaller than n (say, U = o(n) using little-o notation), then you could use base U to get a runtime of Θ(n), essentially because you're back to a standard counting sort here.

As you can see, changing the base really can make quite a difference! I recommend playing around with this in practice to see how well the theory actually ends up working.