# 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 – Martin Källman Jul 18 '14 at 13:51

Unlike radix sort, quicksort is universal, while radix sort is only useful for fix length integer keys.

Also you have to understand, 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. – Martin Källman 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 – Martin Källman Jul 18 '14 at 13:46

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.

-
Actually, quicksort requires `O(n^2)` memory in the worst case due to `n` recursive calls on the left and right partitions. If the implementation uses tail recursion optimization, that can be lowered to just `O(n)` since the calls to the right partition won't require extra space. (en.wikipedia.org/wiki/Quicksort#Space_complexity) – Splinter of Chaos Mar 10 '15 at 13:01

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

-