Radix Sort

Here are the key explanation of Radix Sort:

• Radix Sort is a linear sorting algorithm that sorts elements by processing them digit by digit. It is an efficient sorting algorithm for integers or strings with fixed-size keys.
• Radix sort is the linear sorting algorithm that is used for integers. In Radix sort, there is digit by digit sorting is performed that is started from the least significant digit to the most significant digit.

Note − If the elements do not have same number of digits, find the maximum number of digits in an input element and add leading zeroes to the elements having less digits. It does not change the values of the elements but still makes them k-digit numbers.

Radix Sort Algorithm:

The radix sort algorithm makes use of the counting sort algorithm while sorting in every phase. The detailed steps are as follows −

Step 1 − Check whether all the input elements have same number of digits. If not, check for numbers that have maximum number of digits in the list and add leading zeroes to the ones that do not.

Step 2 − Take the least significant digit of each element.

Step 3 − Sort these digits using counting sort logic and change the order of elements based on the output achieved. For example, if the input elements are decimal numbers, the possible values each digit can take would be 0-9, so index the digits based on these values.

Step 4 − Repeat the Step 2 for the next least significant digits until all the digits in the elements are sorted.

Step 5 − The final list of elements achieved after kth loop is the sorted output.

Example:

For the given unsorted list of elements, 181, 289, 390, 121, 145, 736, 514, 212 we need to perform the radix sort and obtain the sorted output list −

Step 1:

In the first step, the list is sorted on the basis of the digits at 0’s place.

Step 2:

In this step, the list is sorted on the basis of the next significant digits (i.e., digits at 10^th place).

Step 3:

In this step, the list is sorted on the basis of the next significant digits (i.e., digits at 100^th place).

Now, the array is sorted in ascending order.

Radix sort complexity

1. Time Complexity

2. Space Complexity