Why isn't Radix Sort used more often?

Question

It's stable and has a time complexity of O(n). It should be faster than algorithms like Quicksort and Mergesort, yet I hardly ever see it used.

Answer 1

That O(f(n)) really means in order of K*f(n), where K is some arbitrary constant. For radix sort this K happens to be quite big (at least order of number of bits in the integers sorted), on the other hand quicksort has one of the lowest K among all sorting algorithms and average complexity of n*log(n). Thus in real life scenario quicksort will be very often faster than radix sort.

Answer 2

Most sorting algorithms are general-purpose. Given a comparison function, they work on anything, and algorithms like Quicksort and Heapsort will sort with O(1) extra memory.

Radix sorting is more specialized. You need a specific key that's in lexicographic order. You need one bucket for each possible symbol in the key, and the buckets need to hold a lot of records. (Alternately, you need one big array of buckets that will hold every possible key value.) You're likely to require a lot more memory to do radix sort, and you're going to use it randomly. Neither of this is good for modern computers, since you're likely to get page faults like Quicksort will get cache misses.

Finally, people don't in general write their own sort algorithms any more. Most languages have library facilities to sort, and the right thing to do is normally to use them. Since radix sort isn't universally applicable, typically has to be tailored to the actual use, and uses lots of extra memory, it's hard to put it into a library function or template.

Answer 3

I use it all the time, actually more than comparison-based sorts, but I'm admittedly an oddball that works more with numbers than anything else (I barely ever work with strings, and they're generally interned if so at which point radix sorting can be useful again to filter out duplicates and compute set intersections; I practically never do lexicographical comparisons).

A basic example is radix sorting points by a given dimension as part of a search or median split or a quick way to detect coincident points, depth sorting fragments, or radix sorting an array of indices used in multiple loops to provide more cache-friendly access patterns (not going back and forth in memory only to go back again and reload the same memory into a cache line). There's a very wide application at least in my domain (computer graphics) just for sorting on fixed-sized 32-bit and 64-bit numeric keys.

One thing I wanted to pitch in and say is that radix sort can work on floating-point numbers and negatives, though it's difficult to write an FP version that is as portable as possible. Also while it's O(n*K), K just has to be the number of bytes of the key size (ex: a million 32-bit integers would generally take 4 byte-sized passes if there are 2^8 entries in the bucket). The memory access pattern also tends to be a lot more cache-friendly than quicksorts even though it needs a parallel array and a small bucket array typically (the second can usually fit just fine on the stack). QS might do 50 million swaps to sort an array of a million integers with sporadic random-access patterns. The radix sort can do that in 4 linear, cache-friendly passes over the data.

However, the lack of awareness of being able to do this with a small K, on negative numbers along with floating-point, might very well contribute significantly to the lack of popularity of radix sorts.

As for my opinion on why people don't use it more often, it might have to do with many domains not generally having the need to sort numbers or use them as search keys. However, just based on my personal experience, a lot of my former colleagues also didn't use it in cases where it was perfectly suited, and partially because they weren't aware that it could be made to work on FP and negatives. So aside from it only working on numeric types, it's often thought to be even less generally applicable than it actually is. I wouldn't have nearly as much use for it either if I thought it didn't work on floating-point numbers and negative integers.

Some benchmarks:

Sorting 10000000 elements 3 times...

mt_sort_int: {0.135 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

mt_radix_sort: {0.228 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

std::sort: {1.697 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

qsort: {2.610 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

And that's just with my naive implementation (mt_sort_int is also radix sorting but with a faster branch of code given that it can assume the key is an integer). Imagine how fast a standard implementation written by experts might be.

The only case where I found the radix sort to fare worse than C++'s really fast comparison-based std::sort was for a really small number of elements, say 32, at which point I believe std::sort starts using sorts better suited for the smallest number of elements like heapsorts or insertion sorts, though at that point my implementation just uses std::sort.

Answer 4

It's quite rare that the keys you sort by are actually integers in a known, sparse range. Usually you have alphabetic fields, which look like they would support non-comparative sorting, but since real-world strings aren't distributed evenly across the alphabet, this doesn't work as well as it should in theory.

Other times, the criterion is defined only operationally (given two records, you can decide which comes first, but you cannot assess how a 'far' down the scale an isolated record is). So the method is often not applicable, less applicable than you might believe, or just not any faster than O(n * log (n)).

Answer 5

One more reason: These days sorting is usually implemented with a user-supplied sorting routine attached to compiler-supplied sort logic. With a radix sort this would be considerably more complex and gets even worse when the sort routine acts upon multiple keys of variable length. (Say, name and birthdate.)

In the real world I have actually implemented a radix sort once. This was in the old days when memory was limited, I couldn't bring all my data into memory at once. That meant that the number of accesses to the data was far more important than O(n) vs O(n log n). I made one pass across the data allocating each record to a bin (by a list of which records were in which bins, not actually moving anything.) For each non-empty bin (my sort key was text, there would be a lot of empty bins) I checked if I could actually bring the data into memory--if yes, bring it in and use quicksort. If no, build a temp file containing only the items in the bin and call the routine recursively. (In practice few bins would overflow.) This caused two complete reads and one complete write to network storage and something like 10% of this to local storage. Simply quicksorting the whole file would I believe cause about 2 * n log n reads and about half as many writes--considerably slower.

These days such big-data issues are far harder to run into, I will probably never write anything like that again. (If I was faced with the same data these days I would simply specify 64-bit OS, add RAM if you get thrashing in that editor.)

Answer 6

If all your parameters are all integers and if you have over 1024 input parameters, then radix sort is always faster.

Why?

Complexity of radix sort = max number of digits x number of input parameters.

Complexity of quick sort = log(number of input parameters) x   number of input parameters

So radix sort is faster when

log(n)> max num of digits

The max integer in Java is 2147483647. Which is 10 digits long

So radix sort is always faster when

log(n)> 10

Therefore radix sort is always faster when n>1024