Radix Sort

Radix sort is a sorting technique in which we sort the numbers by place value or position of that digit in that number. To perform sorting on numbers you have to start from least significant digit to most significant digit.
Let’s say number is ‘341‘ then we will start from the digit 1.
Whereas to perform sorting in string we generally start from most significant digit.
Let’s say name is ‘Adam‘ then we will start from alphabet A.
Please go through the “Count Sort” first if you have not learn it before as Radix sort follow Count Sort as subroutine.

Consider the list of numbers :
3, 265, 403, 155, 80, 56
We have maximum 3 digit number in the number series, So we firstly prepend 0 in one or two digit number. So, our number series becomes:
003, 265, 403, 155, 080, 056

As these all are decimal number and a decimal number has base 10. So, to understand the logic behind it we can say we will use 10 buckets that hold numbers depending upon their place values. This is the reason, we also resemble it with the name Bucket sort. But in the main memory Stack and Queue operations are used to accomplish this sorting.
Let’s create buckets and perform sorting:
Step 1:
Pass 1: We will start from 1’s place least significant digit and put it in the bucket that resembles with the bucket number.

0	080
1
2
3	003,403
4
5	265,155
6	056
7
8
9

Now we will pop or remove these values starting from the top of the bucket and number series becomes:
080, 003, 403, 265, 155, 056
Step 2:
Pass 2: Next we will take 10’s place digit and put it in the bucket that resembles with the bucket number.

0	003,403
1
2
3
4
5	155,056
6	265
7
8	080
9

Now we will pop or remove these values starting from the top of the bucket and number series becomes:
003, 403,155, 056,265,080
Step 3:
Pass 3: Next we will take 100’s place digit and put it in the bucket that resembles with the bucket number.

0	003,056,080
1	155
2	265
3
4	403
5
6
7
8
9

Again pop all elements from the bucket and we get the sorted series:

003, 056, 080, 155, 256, 403

Program: