Return to my Computer pages
Go to my home page
© Copyright 1999, Jim Loy
Many years ago, I read two articles in computer magazines, which claimed that the Radix Sort was the fastest of all sorting methods. Radix Sort is among the fastest methods, but it is well-known that, in general, Quick Sort is faster. Sorting methods come in two general types, n-squared and n-log-n. An "n-squared method" means that given a list of n elements, the amount of time that such a method takes to sort the list is proportional to n-squared. These are the slow sorts, like Insertion Sort, Selection Sort, and the famous (and really slow) Bubble Sort. The faster sorts are called n-log-n because their speed is proportional to n times log(n), where the log is the base 2 log (not base 10 or e as in the mathematical world). Some of these sorts are Binary Tree Sort, Merge Sort, Quick Sort, Shell's Sort, and Heap Sort. The articles, which I mentioned above, claimed that the Radix Sort is an n sort, in other words that it is proportional to n, the number of elements in the list. If this were true, then Radix Sort would indeed be the fastest, if the lists that you want to sort are long enough. It turns out that this is a natural mistake.
I will perform a short Radix Sort for you. Here is a list that I want to sort. With Radix sort, we use a binary key. To the right, I have typed the decimal version of this binary key.
110011 51 101001 41 010011 19 000110 6 110000 48 011001 25 010111 23
We start by sorting on the last (lowest ordered) bit (otherwise keeping the list in order):
v
000110 6
110000 48
110011 51
101001 41
010011 19
011001 25
010111 23
I typed a little "v" to show you which bit we were currently working on. Here we end up with two elements with zeros as the right-most bit, followed by all of the elements with ones as the right-most bits. Now we sort on the next bit:
v
110000 48
101001 41
011001 25
000110 6
110011 51
010011 19
010111 23
The third bit:
v
110000 48
101001 41
011001 25
110011 51
010011 19
000110 6
010111 23
The fourth:
v
110000 48
110011 51
010011 19
000110 6
010111 23
101001 41
011001 25
The fifth:
v 000110 6 101001 41 110000 48 110011 51 010011 19 010111 23 011001 25
The sixth:
v 000110 6 010011 19 010111 23 011001 25 101001 41 110000 48 110011 51
And it is sorted, seemingly by magic, as it seemed to be rather unsorted before the last step.
It turns out that the speed of the Radix Sort is indeed proportional to n, for any given length of key. And that phrase "for any given length of key" is the fly in the ointment. We sorted our list in six steps. If we wanted to sort a much longer list, we would probably need a longer key. And we would be foolish to sort a small list with a long key; so we would probably need a shorter key in that case. A short list takes four or five steps (we could have used a shorter key above), and a long list may take 20 or 30 steps. It turns out that the length of key needed is proportional to the base 2 log(n). And that makes the Radix Sort an n-log-n sort. Too bad.
The Radix Sort is useful when there are fast ways to compare binary keys, as in Assembly languages. You also need a relatively small binary key, already formed. Keys like lastname+firstname are way too long.