When should we use Radix sort?
It seems Radix sort has a very good average case performance, i.e. O(kN): http://en.wikipedia.org/wiki/Radix_sort
Yet it seems like most people are still using Quick Sort - why is this?
Solution 1:
Radix sort is harder to generalize than most other sorting algorithms. It requires fixed size keys, and some standard way of breaking the keys into pieces. Thus it never finds its way into libraries.
Solution 2:
The other answers here fail to give examples of when radix sort is actually used.
An example is when creating a "suffix array" using the skew DC3 algorithm (Kärkkäinen-Sanders-Burkhardt). The algorithm is only linear-time if the sorting algorithm is linear-time, and radix sort is necessary and useful here because the keys are short by construction (3-tuples of integers).
Solution 3:
Edited according to your comments:
- Radix sort only applies to integers, fixed size strings, floating points and to "less than", "greater than" or "lexicographic order" comparison predicates, whereas comparison sorts can accommodate different orders.
- k can be greater than log N.
- Quick sort can be done in place, radix sort becomes less efficient.
Solution 4:
Unless you have a huge list or extremely small keys, log(N) is usually smaller than k, it is rarely much higher. So choosing a general-purpose sorting algorithm with O(N log N) average case performance isn't neccesarily worse than using radix sort.
Correction: As @Mehrdad pointed out in the comments, the argument above isn't sound: Either the key size is constant, then radix sort is O(N), or the key size is k, then quicksort is O(k N log N). So in theory, radix sort really has better asymptotic runtime.
In practice, the runtimes will be dominated by terms like:
radix sort: c1 k N
quicksort: c2 k N log(N)
where c1 >> c2, because "extracting" bits out of a longer key is usually an expensive operation involving bit shifts and logical operations (or at least unaligned memory access), while modern CPUs can compare keys with 64, 128 or even 256 bits in one operation. So for many common cases, unless N is gigantic, c1 will be larger than c2 log(N)
Solution 5:
Radix sort takes O(k*n) time. But you have to ask what is K. K is the "number of digits" (a bit simplistic but basically something like that).
So, how many digits do you have? Quite answer, more than log(n) (log using the "digit size" as base) which makes the Radix algorithm O(n log n).
Why is that? If you have less than log(n) digits, then you have less than n possible numbers. Hence you can simply use "count sort" which takes O(n) time (just count how many of each number you have). So I assume you have more than k>log(n) digits...
That's why people don't use Radix sort that much. Although there are cases where it's worthwhile using it, in most cases quick sort is much better.