4
$\begingroup$

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?

$\endgroup$

migrated from cstheory.stackexchange.com Feb 6 '14 at 16:01

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 3
    $\begingroup$ With what I wrote on my blog you get that you should use $\approx2^{4.196}$ buckets for 1 million integers. On a real computer you also have caching to worry about. That's probably why $2^3$ buckets turn out to work better than $2^4$ buckets. $\endgroup$ – rgrig Jan 13 '14 at 7:04
  • $\begingroup$ What the calculation gives is that the best choice of $r$ is roughly $c\log n$ for some constant $c$. The choice of $c$ only affects the result by a constant factor, but you care about constant factors. Have you tried seeing which choice of $r$ maximizes $(b/r)(n+2^r)$? $\endgroup$ – Yuval Filmus Feb 6 '14 at 17:40
  • $\begingroup$ I'd take a look at Knuth's "Sorting and searching", he gets precise answers to running times (not just $O()$ type results). $\endgroup$ – vonbrand Feb 8 '14 at 0:48
  • $\begingroup$ Sorting one million 32-bit integers needs O(1) time, no matter what algorithm you choose. You should also fix your machine model. I assume you mean a real machine? $\endgroup$ – adrianN Jun 16 '16 at 7:16
1
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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%.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.