Radix Sort with example

1

Radix Sort :

If you are struggling to learn sorting algorithms? Don't worry here you go....This page will explain radix step by step.

First Pass:

Data: 67 50 70 25 93 47 21

Buckets on first pass (least significant digit):
index  0 1 2 3 4 5 6 7 8 9
count  2 1 0 1 0 1 0 2 0 0
offset 0 2 3 3 4 4 5 5 7 7

Data after first pass
       50 70 21 93 25 67 47

That data is created by doing a single pass on the unsorted data, using the offsets to work out at where each item belongs.
For example, it looks at the first one 67, then at the offsets for the digit 7, and inserts it into the 5th position. The offset at 7 is then incremented, so that the next value encountered which has a least significant digit of 7 is placed into the 6th position. Continuing the example, the number 50 would then be looked at, and inserted into the 0th position, its offset incremented, so that the next value which is 70 would be inserted into the 1st position, and so on until then end of the list.
As you can see, this data is sorted by its least significant digit.

Second Pass:

Data after first pass
      50 70 21 93 25 67 47

Buckets on first pass (most significant digit):
index  0 1 2 3 4 5 6 7 8 9
count  0 0 2 0 1 1 1 1 0 1
offset 0 2 3 3 4 4 5 5 7 7

Data after second pass (sorted)
       21 25 47 50 67 70 93

Look at this diagram for another example, noting that the "offsets" array is unnecessary