Select Page

Radix sort in Java uses the digits of the numbers given in the sorted array to sort the numbers. The radix sort uses the place value of digits to do the sorting moving from the LSB (Least Significant Digit) to MSB (Most Significant Digit) of the numbers. By using the counting sort, the quick sort place elements to their appropriate position. Unlike other sorting algorithms, this sorting algorithm never compares numbers to do the sorting. Hence, radix sort is a non-comparative sorting algorithm.

Algorithm and Pseudo Code

Java Program
The following code implements radix sort using the pseudo-code defined above.

Output:

Explanation: The above program first does the sorting of digits present at the unit place. Then, it performs the sorting again, using counting sort, on the digits present at tens place that is already sorted with the digits present at the unit place. Finally, the program takes the digits present at the hundredth place and does the sorting using counting sort. For simplicity, we have taken all numbers having the same number of digits. The following diagram illustrates the same.

If elements are having a different number of digits, 0 is padded to the element that has a smaller number of digits. For example, if we take 9, 343, 34 then, 9 is considered as 009, 343 as 343, and 9 as 009. Thus, we end up having an equal number of digits for each number.

Radix sort is a stable sorting algorithm. It uses the concept of bucketing for placing numbers having the same LSB or MSB in the same bucket. Then counting sort decided which number to put first and which one to put later in the bucket. For a large number of inputs, it is found that the radix sort is better than quick sort. However, it is not completely true. If the number of digits increases, then quick sort takes precedence over radix sort.

Time Complexity

Let dig be the number of digits of the largest value element. Let, n be the number of elements in the given input array. Then, the total time complexity of radix sort is O(dig(n + b)), where b is the base used to represent the numbers. In our example, numbers are represented in base 10.

Space Complexity

Space complexity of the radix sort is O(n + k), where n is the total number of elements present in the array, and k is the number of digits present in the maximum element.

Conclusion

Even though the radix sorting algorithm works well than comparison algorithm, for larger numbers the radix sort operation is slow. It should be used where it is required to bucket the elements of almost same category. For lexicographical sorting of strings, the radix sort algorithm can also be used.