# Why isn't Radix Sort used more often?

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.

• See here: en.wikipedia.org/wiki/Radix_sort#Efficiency The efficiency is O(kn) and it may not be better than O(n*log(n)). – FrustratedWithFormsDesigner May 19 '11 at 14:09
• Radix sort is frequently used in soft real-time systems such as games. Whether or not one algorithm outperforms another is, as usual, dependent on all the parameters of the problem, not just the complexity bound – awdz9nld Jul 18 '14 at 13:51
• @FrustratedWithFormsDesigner Perhaps the wiki has changed? I don't see the reference to nlog(n) anymore, FWIW... – rogerdpack Nov 12 '19 at 19:40
• Boost has an (in place variant) of it: boost.org/doc/libs/1_62_0/libs/sort/doc/html/sort/sort_hpp.html but yeah, I think people just don't know it exists...either that or they all just use the "standard" sorting algorithm which, for whatever reason, framework creators tend to still re-use the "generic" sorts that aren't as efficient...maybe they aren't focused on sorting ints typically, since it's a rarer use case? – rogerdpack Nov 12 '19 at 20:57
• – FrustratedWithFormsDesigner Jan 27 '20 at 16:49

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.

• Note on the complexity stated: although (LSD) Radix sort has a complexity of O(n*K), this constant is usually small, typically chosen such that (2^(W/K))*C fits into L1, where C is the size in bytes of the counter, W the size of the key being sorted. Most implementations choose K=[3,4] for 32-bit words on x86. K can also be made adaptive to exploit temporal coherence (near-sortedness), as each radix is sorted individually. – awdz9nld Jul 18 '14 at 13:45
• Note on universality: Radix sort is fully capable of operating on floating-point keys, as well as variable-length integer keys – awdz9nld Jul 18 '14 at 13:46
• This is a bit misleading: 1) "at least order of number of bits" should actually be "at most". For example, if you choose 8-bits wide digits when sorting 32-bit integers, presuming counting sort is used for each radix, it means 256 counting slots or 4 passes through the array to count and 4 passes to sort. That's K == 8 even if sorting millions of items. 2) Quicksort's "K" is actually log2(N) in the average case. Give a tiny 256-element array to Quicksort, and you will get K == 8 passes through the array on average, but ridiculous K=64 passes for the worst case. – Groo Apr 3 '20 at 7:31
• The two major points of this answer are completely incorrect, but it's the accepted and top-voted answer. Is there anything we can do about this? – rd11 Aug 12 '20 at 20:53
• @rd11 feel free to write your own answer – vartec Aug 19 '20 at 21:12

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.

• You need only S(n) \in O(n) space for sorting with radix, i.e. same as for heap or quick sort. – Velda Mar 27 '18 at 8:55
• @SplinterofChaos has the wiki perhaps changed? It doesn't seem to mention n^2 for quicksort anymore, but O(log n) ... – rogerdpack Nov 12 '19 at 19:06
• I don't think it's "a lot" more memory, maybe 2*n (OK that's a lot more but maybe not impossible)? And the buckets are so small (assuming you're splitting on bytes and recursing) that it could fit well into cache? – rogerdpack Nov 12 '19 at 19:31
• @SplinterofChaos The O(n^2) memory is nonsense; even a bad implementation uses O(n) worst case. Sorting the smaller half recursively and the larger half directly takes the space down to O (log n). – gnasher729 Mar 9 at 19:15
• Deleted my comment. Didn't want to be spreading misinformation and the edit button wasn't working. – Splinter of Chaos Apr 2 at 21:19

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 ]

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

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

• Radix sort can handle integers (or strings) in any range by recursively sorting them "a byte at a time" so they don't have to be in a sparse range FWIW... – rogerdpack Nov 12 '19 at 19:29

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

• Fascinating considering one of the disadvantages mentioned to radix sort sometimes mentioned is "it takes more space." Still trying to wrap my head around this... – rogerdpack Nov 12 '19 at 19:12
• @rogerdpack It wasn't that my approach used less space, it's that it used less access to the data. I was sorting a file that was around a gigabyte while dealing with a compiler limit (this was DOS protected mode, not Windows) of a bit under 16mb of total memory use including code and a structure limit of 64kb. – Loren Pechtel Nov 12 '19 at 23:54

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`

• There are hidden constants in implementation details, but basically you're saying "for larger input radix sort is faster" which...should be the case! It's just hard to find use cases for it but when you can... – rogerdpack Nov 12 '19 at 19:15