Make your own free website on Tripod.com
Lecture 7 - Radix Sort

5. Radix Sort

For the present we will look at one further sorting algorithm. This one is different, it is not based on the general algorithm strategy above, but on a totally different method. It is interesting because it requires the absolute minimum amount of space and the minimum amount of data movement, and, most amazing of all, it does no comparisons.

The sorting algorithm is called Radix Sort. It is ideal if you are using linked lists with integer keys. It sorts elements by looking at their KEY values one digit at a time. First it sorts them according to their least significant digit. It sorts the result of this according to the second least significant digit. And carries on like this until, at last, it has sorted according to the most significant digit.

To illustrate this let's start with the list of 3-digit integers.

Write this list vertically on the board, with lots of space to the right.

362 745 885 957 054 786 080 543 012 565

Because the keys consist of base 10 digits we will need an array of 10 buckets (linked lists) indexed by the possible values of the digits.

Draw this to the right of the list:
In the First Pass through the list, we look only at the least significant (rightmost) digit. That's the end of the first pass. It doesn't look like much has really been accomplished, but wait and see! Here is the state of the buckets now.
In the second pass we go through the buckets created in the first pass, doing them in order from 0 to 9, and, within each bucket, from first to last. In this pass we look only at the middle digit. That's the end of the second pass. It still doesn't look like much has really been accomplished - be patient. Here is the state of the buckets now.
Now for the third pass. This is the final one, because each number has three digits. If there were more digits we'd just continue in the same manner digit by digit from right to left. Believe it or not, when we finish this pass the numbers will be sorted.

In this pass we look only at the high order (leftmost) digit.

We are now completely finished sorting. All we have to do is join up all the lists in all the buckets in order to create the final sorted list.
It should be clear that the amount of work (adding things to the end of the lists in the buckets, and removing things from the front of these lists) is proportional to:

(Length of the original list) * (number of digits)