1. A radix sort is a technique for sorting nonnegative integers (or other data that has individual characters or digits). One version of radix sort works with a linked list of integers. In addition to the list that is being sorted, there are two extra lists called list0 and list1. The algorithm begins by going through the list of elements to be sorted; every even number is transferred from the original list to the tail of list0, and every odd number is transferred to the tail of list1. After all numbers have been processed, put the two lists together (with list0 in front and list1 at the back), and then put the whole thing back in the original list.
This process of separating and splicing is repeated a second time, but now we separate based on the boolean expression ((n/2) % 2 == 0). And then we separate and splice using ((n/4) % 2 == 0). And so on, with larger and larger divisors 8, 16, 32, ..., . The process stops when the divisor is bigger than the largest number in the list. Here is one way to implement the algorithm for ordinary integers (with a maximum value of 231—1):
To improve performance, you can break out of the loop if the divisor ever exceeds the largest number in the list. But if you don’t do so, the loop will still end when the divisor overflows the largest possible integer.
The algorithm is quick: Each iteration of the loop takes
O(n) time (where
n
is the size of the list), and the total number of iterations is about log2
m
(where
m
is the maximum number in the list). Thus, the entire time is
O(n
log
m).