Another very popular sorting algorithm is radix sort as it is really fast on sequential machines. The fundamental policy of radix sort is that each element is sorted digit by digit. Let's look at a simple example to explain the steps involved in radix sort:
Suppose the elements to be sorted are as follows:
| Value | 7 | 14 | 4 | 1 |
The equivalent binary values of these numbers are as follows:
| Bits | 0111 | 1110 | 0100 | 0001 |
The first step is to sort based on bit 0. Bit 0 for the numbers are as follows:
| 0th Bit | 1 | 0 | 0 | 1 |
To sort based on the oth bit basically means that all the zeroes are on the left. All the ones are on the right while preserving the order of elements:
| Sorted value on 0th bit | 14 | 4 | 7 | 1 |
| Sorted bits based on 0th bit | 1110 | 0100 | 0111 | 0001 |
After the 0th bit is done, we move on to the first bit. The...