Algorithm

In radix sort, we sort numbers according to the digits i.e. from LSD [Least Significant Digit] to MSD [Most Significant Digit]. Instead of directly comparing numbers (like in comparison-based sorts), we group numbers based on the current digit, ensuring that earlier sorted digits remain in order thanks to a stable sorting method (commonly counting sort). By the time we finish processing the most significant digit, the entire array is sorted.

Following modifications are done in the counting sort algorithm to make it work accordingly.

1. Declare a count array of size b, where b denotes the base of the numbers in the array.
2. Instead of directly using array elements as index in our count array, we use the digits as index in our count array.
3. Other steps remain the same as a general purpose counting sort algorithm.

Identify the largest value in the array. This determines the total number of passes needed, as each pass corresponds to one digit position from right to left.

Determine the number of digits in the largest value. This will be the total number of passes to perform.
For each pass, focus on one digit position at a time, starting from the units place and moving towards higher place values.
Create a counting structure with a fixed size equal to the number of possible digit values.

Scan through the array and record how many elements have each possible digit at the current place value./li>
Update the counting structure so that each position holds the total number of elements with digits up to and including that position.

Build a new ordered array by placing each element into its correct position based on the current digit, working from the last element to the first to maintain stability.

Copy the ordered array back into the original structure to prepare for the next pass. Repeat the process for the next digit position until all passes are complete.

After the final pass, the collection will be fully sorted in ascending order.

Code