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
add comment

3 Answers

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