When should we use Radix sort?

Question

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

Quick sort has an average of O(N logN), but it also has a worst case of O(N^2), so even due in most practical cases it wont get to N^2, there is always the risk that the input will be in "bad order" for you. This risk doesn't exist in radix sort. I think this gives a great advantage to radix sort.

Solution 2

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 3

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 4

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 5

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)

View more solutions

Comments

[Doc Brown]

Most people use a sort routine provided by their preferred framework without even caring about the algorithm.

[tintin]

Radix sort is not good with different kind of data, but when you want to sort unsigned int and you want are doing the sort on a multi-core processor like GPU, radix sort is faster.

[Steve Jessop]

"Quick sort can be done in place" - so can binary radix sort, although that increases the likelihood that k is greater than log N.

[Mark Ransom]

Your first point is not quite correct - Radix sort can easily be applied to fixed length strings. And the comparison predicate is required no matter which sort algorithm you use.

[Niki]

"Radix sort only applies to integers": Why? I always thought if you sort by the exponent bits and the mantissa bits in the right order, you can use it to sort floating points number, too. And in theory, you could use it on strings, only k will almost always be greater than log N then.

[Alexandre C.]

@Steve, @Mark, @nikie: taken your comments into account. Thanks.

[Ankit Roy]

Quicksort cannot technically be done in-place -- O(log n) extra space is required to record the position of each pivot. (Usually masked because it's stored in a local variable and recursion is used.)

[Niki]

@j_random_hacker: Technically storing an index into an array of length N takes log(N) bits, so I don't think any sorting algorithm can be implemented without extra space ;-)

[Mark Ransom]

This is not true for all cases. k needn't be a bit count, it could be a byte count for example - if you're sorting 4-byte integers, N would need to be smaller than 16 for log N to be less than 4.

[Ankit Roy]

@nikie: If you count bits instead of log(n)-bit words then yes, log(n) bits will be needed to hold an array index, but the original input is now of size n*log(n) instead of n, and quicksort now requires O(log(n)^2) extra bits of space -- while e.g. heapsort requires only O(log n) extra bits. (But you would normally assume a "word RAM" model in which a machine word can hold n in O(1) space, and divide all quantities through by log(n).)

[Steve Jessop]

@j_random_hacker: this is where practicality runs up against theory and both lose. If you're assuming a fixed upper limit on the size of the input array (so that an index can be held in O(1) space), then you break the theoretical model of a limit at infinity, so it's just a question of what you salvage. If you're saying that log(n) is "really" constant, you could just as well say that log^2(n) is "really" constant. In practice, I've written a quicksort (for production) that used, instead of the call stack, a fixed-size array on the stack to store the "todo list". 240 bytes or whatever.

[Ankit Roy]

@Steve Jessop: I hear you. I went on a wild goose chase looking for a definitive answer to this, but the only (murky, unsatisfying) picture that emerged is that when making Big-O time/space statements people usually assume a word RAM model and that a word is at least log(n) bits. Meaning that yes, the machine capacity is implicitly assumed to scale with the input size, which is absurd, though possibly less absurd than other ways to formulate the problem. In any case there's still a log(n) factor difference in the extra space needed by quicksort and heapsort for large-enough n.

[Eldritch Conundrum]

It's unlikely to be the main advantage. Other comparison-based sorts (like heapsort or mergesort) do not have such a bad worst-case behavior as quicksort's.

[huseyin tugrul buyukisik]

Wouldnt radix-256 need 256 times memory of the size of original array?

[Ivan Š]

Completely agree. No mentions of when it's actually used, and no real world benchmarks which compare the two algorithms.

[nburk]

the worst case scenario for quicksort isn't really an argument since that's why people commonly use randomized quicksort, i.e. shuffle the input data before actually sorting it. this practically eliminates the chance of having an N^2 running time.

[user541686]

Introsort, which uses quicksort, takes care of this. This isn't an argument.

[user541686]

O(N log N) is a lie. There is no such thing. It's O(k N log N) vs. O(k N) -- if you don't believe me, ask yourself how in the world sorting could be independent of element size.

[Niki]

@Mehrdad: That seems like an argument about semantics. The way I've learned it, the N in O(N log N) is the size of the input, e.g. in bits. Then either the elements have constant size, or there are only N/k elements.

[user541686]

@nikie: sure, if you consider k to be constant then that's fine, but then radix sort is O(N), not O(k N). Either way you're not supposed to compare k against log N.

[Niki]

@Mehrdad: I see your point. Thanks for the correction, I've updated my answer.

[user541686]

Great! Removed my -1 :) I've actually done the analysis before, it's a great exercise and getting nontrivial... if you have the time I suggest you go through it, because there is a crossover that you can indeed determine (at least if you neglect cache effects), but it's not as simple as k vs. log N.

[zhuwenbin]

no, as you can see in the codes, it need only bar[256] and s[original.length], it's additional 1 times memory of the original array

[Linear]

Note: Radix sort is a string sorting algorithm, not numeric. Well, okay, it's a lexicographic sorting algorithm. "Radix" means "base" (as in base 10 or base 8), and it can sort anything that has digits and places with a predefined order, and that includes strings as long as you choose an order for the characters (e.g. alphabetic, ASCII, unicode codepoint, whatever). You can even think of an English dictionary as a 26 bucket radix sort of English words if you want. I say it's a string sort because as far as computer representations go it's closer to treating the num like a string of digits.

[Admin]

@LinearZoetrope You're right! My bad for my crudeness there. Actually now I'm curious if a radix sort of short strings in a lexicographic fashion might outperform, say, introsort. I really find radix sorts indispensable but can see why many standard libs might omit it given the requirements for more than just a comparator.