title: Choosing the optimal radix/number-of-buckets when sorting n-bit integers using radix sort
body: <p>This is a popular question: What is the most efficient (in time complexity) way to sort 1 million 32-bit integers. <a href="http://www.quora.com/Sorting-Algorithms/What-is-the-most-efficient-way-to-sort-a-million-32-bit-integers" rel="nofollow">Most answers</a> 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. </p>
  
  <p><a href="http://www.quora.com/Sorting-Algorithms/What-is-the-most-efficient-way-to-sort-a-million-32-bit-integers" rel="nofollow">In this observed answer</a>, the selection of the radix/number of buckets was done empirically and it turned out to be 2^8 for 32bits 1million 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 Big 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 &lt;= b, radix-sort sorts the number in Big Theta((b/r)(n+2^r)) time. It then says: "If b>= floor(lg(n)), choosing r ~= floor(lg(n)) gives the best time to within a constant factor...". </p>
  
  <p>But, if we choose r=lg(1million)~=20 != 8 as the observed answer suggests. </p>
  
  <p>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.</p>
  
  <p>Could anyone clear this up for me? Thank you in advance.</p>