Radix Exchange Sort , Straight Radix Sort & Induction

Radix Exchange Sort :

Sorts beginning from the most significant digit and then for each list, inductively sort the remaining digits by forming lists within each list . For eg, to sort : 12 45 67 22 14 6 23 90 11

First form lists from 0 to 9 for the 10's place :
0 : 06
1 : 12 14 11
2 : 22 23
3 :
4 : 45
5 :
6 : 67
7 :
8 :
9 : 90

Then for each list, form lists within for the unit's place
For eg, for list 1 : ( lists based on unit's place )
0 :
1 : 11
2 : 12
3 :
4 : 14
5 :
Now read off all numbers in order : 06 11 12 14 22 23 45 67 90

Straight Radix Sort :

This is the traditional sorting taught in class based on sorting beginning at the least significant digit. The point here to note is that you need to form a list of numbers one for each kind of digit ( 10 lists for the decimal system ) only once and then you need one more queue for holding the numbers at the end of each pass.

This sorting is based on induction in the sense : Assume you have sorted the least i digits and now you have two numbers starting at the (i + 1)th digit as u = a[i digits] and v = b[i digits] with a = b . Now since u and v are sorted in the least i digits , if [ i digit - u] < [ i digit - v ] then u would precede v in the queue already and the current sort phase would not disturb the order in this pass and hence it would remain sorted.

For eg if u = 6789 and v = 6098 , then in the queue v would precede u ( as 098 < 789 ) and in this phase first v would be put in list 6 followed by u. Hence the numbers would remain sorted.

Its complexity is O(kn) where k is the max # of digits in any input number and n is the total size of input ( k passes, at every pass , all numbers are relocated )