Please read the question and answer completly.

A radix sort is a technique for sorting unsigned integers (or other data has individual character or digits).

One version of radix sort works with a linked list of unsigned 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 evey odd number is transferred to the tail of list1. (If you are using STL list class, you may add a new node to the tail of a list with push_back). After all numbers have been porcessed, pupt the two lists together (with list0 in front and list1 at the back), and then put the whole thing back in the original list. With the STL list class, this can be done in constant time with two splice statements shown here:

splice (original.begin(), list1); splice (original.begin(), list0);

In this code, original is the original list (that is empty before the two splices because we moved everything to list0 anf list1). The 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 ((n/4) % 2 == 0). And so on with larger and larger divisiors 8, 16, 32,... . The process stops when divisor is bigger than the largest number in the list.

Here is one way to implement the algorithm:

const int MAX_ITERATIONS = sizeof(unsigned int)*8; divisor = 1; for(i = 0; i < MAX ITERATIONS; ++i) { Perform the separation and splice using the ((n/divisor)%2 == 0) to control the split. divisor = 2*divisor; }

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 the divisor overflows the largest possible unsigned integer. If you are familiar with the bit-shift operator >> on numbers, then a slightly more efficient expressions is ((n>>i) % 2 == 0). Another efiicient alrenative uses the bitwise & operator (written with one & rather than &&); (n & divisor == 0). 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).

Thanks!