Choosing the optimal radix/number-of-buckets when sorting n-bit integers using radix sort

Question

This is a popular question:

What is the most efficient (in time complexity) way to sort 1 million 32-bit integers?

Most answers seem to agree that one of the best ways would be to use radix sort since the number of bits in those numbers is assumed to be constant. This is also a very common thought exercise when CS students are first learning non-comparison based sorts. However, what I haven't seen described in detail (or at least clearly) is how to optimally choose the radix (or number of buckets) for the algorithm.

In this observed answer, the selection of the radix/number of buckets was done empirically and it turned out to be $2^8$ for 1 million 32-bit integers. I'm wondering if there is a better way to choose that number? In "Introduction to Algorithms" (p.198-199) it explains Radix's run-time should be $\Theta(d(n+k))$ (d=digits/passes, n=number of items, k=possible values). It then goes further and says that given n b-bit numbers, and any positive integer $r \leq b$, radix-sort sorts the number in $\Theta((b/r)(n+2^r))$ time. It then says:

If $b \geq \lfloor \lg(n) \rfloor$, choosing $r = \lfloor \lg(n) \rfloor$ gives the best time to within a constant factor.

But, if we choose $r = \lg(10^6) =20$, which is not $8$ as the observed answer suggests.

This tells me that I'm very likely misinterpreting the "choosing of $r$" approach the book is suggesting and missing something (very likely) or the observed answer didn't choose the optimal value.

Could anyone clear this up for me?

Answer 1

Minimizing run time is a very different question from minimizing operation counts. Sorting large data sets tends to be memory bound, so the goal of optimization is not to reduce the number of operations, but to try and do make efficient use of memory — for example,

• do as much work as possible in L1 cache
• use bandwidth to main memory efficiently by writing full cache lines
• avoid overflowing the TLB by too much

Increasing the number of buckets works against all three points; it does no good to complete a radix sort in two passes if each pass takes three times as long as each pass of a four pass implementation!

Answer 2

The derivative of (b/r)(n+2^r) = (b (2^r (r ln(2) - 1) - n))/r^2. A minimum occurs when the derivative == 0, which occurs when 2^r (r ln(2) - 1) - n = 0. For n == 2^20 (about 1 million), r ~= 16.606232 results in O() ~= 2212837. Some example values and O():

 r   O
18   2330169
17   2220514
16   2228224
15   2306867
12   2807125

So r = 16 would be the best actual number based on the formula. However since L1 cache is typically 32 KB, the optimal values for r are less. On my system (Intel 2600K 3.4 ghz), for n = 2^20, then 4 fields of 8, 8, 8, 8 (r = 8) is fastest. At around n = 2^24 3 fields of 10, 11, 11 (r = 10.67) is fastest. At around n = 2^26, 2 fields of 16, 16 (r = 16) is fastest. There's not a lot of difference though, less than 10%.