35.2 LSD Radix Sort

Least Significant Digit Radix Sort -- Using Count Sort

Notice in the above picture that we had a completely random input of numbers 22, 34, 41, etc. Then in the second box, we had sorted by right most digit, so 41, 41, 31 would come first as 1 is the lowest rightmost digit. Next would come 32, 22, 12, as 2 is the second least rightmost digit. Notice that we still have to take care of sorting 32, 22, and 12 which is why we move to the second right most digit in our last box which has everything sorted.

What is the runtime of LSD sort?

• $\Theta(WN+WR)$

• $N$: Number of items, $R$: size of alphabet, $W$: Width of each item in # digits

Non-equal Key Lengths