Choosing the optimal radix/number-of-buckets when sorting n-bit integers using radix sort 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?
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 &mdash; 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!