Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
1  
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 at 13:51
add comment

3 Answers 3

up vote 19 down vote accepted

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.

share|improve this answer
    
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 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 at 13:46
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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