The algorithm operates in O(nk) time, where n is the number of items, and k is the average key length. This algorithm was originally used to sort punched cards in several passes. [A computer algorithm was invented for radix sort in 1954 at M.I.T. by Harold H. Seward.] [In many of the new applications requiring super speeds and massive memory, the computer radix sort supersedes the slower comparison sorts.]
Radix sort has resurfaced as an alternative to other high performance sorting algorithms (like quicksort, heapsort and merge sort) which require O(n lg n) comparisons, where n is the number of items to be sorted. These other algorithms are able to sort with respect to more complicated orderings than lexicographic, but this is of little importance in many practical applications.
If the size of the possible key space is proportional to the number of items, then each key will be lg n symbols long, and radix sort uses O(n lg n) time in this case.
In practice, if the keys used are short integers, it is practical to complete the sorting with only two passes, and comparisons can be done with only a few bit operations that operate in constant time. In this case, radix sort can effectively be regarded as taking O(n) time and in practice can be significantly faster than any other sorting algorithm.
The greatest disadvantages of radix sort are that it usually cannot be made to run in place, so O(n) additional memory space is needed, and that it requires one pass for each symbol of the key, so it is very slow for potentiallylong keys.
Radix sort uses the following sorting order: short keys come before longer keys, and keys of the same length are sorted lexicographically. This coincides with the normal order of numbers, if the numbers are represented as digit strings.
A radix sort algorithm works as follows:
The sort in step 2 is usually done using bucket sort, which works since there are only finitely many digits.
Sort the list:
170, 45, 75, 90, 2, 24, 802, 66
A recursively subdividing radix sort algorithm works as follows:
This recursive method can be interpreted as a generalization of quicksort from strings with two possible symbols to strings with any number of possible symbols.
Search Encyclopedia

Featured Article
