Practical Applications of Radix Sort

Answered By : Wandering Logic

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

• Zagha and Blelloch: Radix sort for vector multiprocessors. Supercomputing, 1991: 712-721.
• Blelloch, Leiserson, Maggs, Plaxton, Smith, and Zagha: A Comparison of Sorting Algorithms for the Connection Machine CM-2. Symp Parallel Algorithms and Arch (SPAA-3):3-16, 1991.
• Arpaci-Dusseau, Arpaci-Dusseau, Culler, Hellerstein, and Patterson: High-performance sorting on networks of workstations. Conf on Mgt of Data, (SIGMOD-1997):243-254.
• Arpaci-Dusseau, Arpaci-Dusseau, Culler, Hellerstein, and Patterson. Searching for the sorting record: experiences in tuning NOW-Sort. ACM Sigmetrics Symp Parallel and Distributed Tools, (SPDT-2):124-133, 1998.

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.

Problem Detail: 

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?

Asked By : Robert S. Barnes

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12223