23
$\begingroup$

Radix sort is theoretically very fast when you know that the keys are in a certain limited range, say $n$ values in the range $[0\dots n^k -1]$ for example. If $k<\lg n$ you just convert the values to base $n$ which takes $\Theta(n)$ time, do a base $n$ radix sort and then convert back to your original base for an overall $\Theta(nk)$ algorithm.

However, I've read that in practice radix sort is typically much slower than doing for example a randomized quicksort:

For large arrays, radix sort has the lowest instruction count, but because of its relatively poor cache performance, its overall performance is worse than the memory optimized versions of mergesort and quicksort.

Is radix sort just a nice theoretical algorithm, or does it have common practical uses?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
17
$\begingroup$

Radix sorts are often, in practice, the fastest and most useful sorts on parallel machines.

On each node of the multiprocessor you probably do something like a quicksort, but radix sort allows multiple nodes to work together with less synchronization than the various recursive sorts.

There are other situations too. If you need a stable sort (a sort where whenever two keys are equal they stay in the same order rather than getting rearranged) then I'm not aware of any version of quicksort that will be of use. Mergesort is also stable (if implemented correctly). Your link is the first time I've ever heard anyone say that mergesort could be made to have better cache behavior than radix sort.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Patterson and Hennessy make the same point as the above linked paper by Lamarca in their book, Computer Organization and Design. $\endgroup$
    – Robert S. Barnes
    May 23, 2013 at 19:07
  • $\begingroup$ Your mention of Patterson reminded me of the important work that Andrea Arpaci-Dusseau did on sorting on clusters about 15 years ago. (Patterson was a co-author). In the 1997 paper they actually decided that partial-radix sort was preferable to quicksort on the individual nodes as well. (I added the references to the answer). $\endgroup$
    – Wandering Logic
    May 25, 2013 at 17:23
  • $\begingroup$ That's interesting. In the 2009 fourth edition of CompOrg they reference Lamarca's work on previous versions of Radix sort being cache unfriendly (pg. 489), but then on page 490 under graphs comparing Quicksort and Radix sort they say, "Due to such results, new versions of Radix sort have been invented that take memory hierarchy into account, to regain its algorithmic advantages." I'm curious how these new versions of Radix Sort operate. $\endgroup$
    – Robert S. Barnes
    May 25, 2013 at 19:33
  • $\begingroup$ My suspicion is that Lamarca just used a stupid radix sort (one that keeps its buckets as linked lists.) No-one would ever do that. You would implement the buckets using some kind of optimized dynamic array (e.g., like a C++ vector). But I don't know, as I haven't read Lamarca's papers. $\endgroup$
    – Wandering Logic
    May 25, 2013 at 19:43
  • $\begingroup$ @WanderingLogic where does radix sort use buckets? Do you mean bucket sort here? $\endgroup$
    – Bar
    Jan 9, 2016 at 13:23
4
$\begingroup$

@Robert: Your link is quite surprising (actually I could not find the quoted sentence). My personal experience is for random input, radix sort is much faster than the STL std::sort(), which uses a variant of quicksort. I used to make an algorithm 50% faster by replacing std::sort() with an unstable radix sort. I am not sure what is the "memory optimized version" of quicksort, but I doubt it can be twice as fast as the STL version.

This blog post evaluated radix sort along with several other sorting algorithms. Briefly, in this evaluation, std::sort() takes 5.1 sec to sort 50 million integers, while in-place/unstable radix sort takes 2.0 sec. Stable radix sort should be even faster.

Radix sort is also widely used for stably sorting strings. Variants of radix sort are at times seen for constructing suffix arrays, BWT, etc.

Improve this answer
$\endgroup$
2
$\begingroup$

Radix sort is also a natural way to sort fixed-length words over a fixed alphabet, e.g. in Kärkkäinen & Sanders algorithm (http://www.cs.cmu.edu/~guyb/realworld/papersS04/KaSa03.pdf)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.