# How to write a Radix sort program in Java

By | July 21, 2020

In this post, we will learn How to write a Radix sort program in Java. Radix sort is in the group of Counting Sort and Bucket Sort which are O(n) sorting algorithms.

How does Radix sort work?

The radix sort usually works by doing the sorting in passes moving from least significant digit to the most significant digit. In each pass, we can use any stable sort to sort the numbers on the digit.

If you have an array inputArr with the maximum element in array inputArr having a number of digits as d, then the working of Radix sort is as shown below.

for i = 1 to d

Use any stable sort (like counting sort)

to sort inputArr on digit d

Steps to writing Radix sort is as follows.

1. First of all, find the maximum number in the input array.
2. Afterward, we have to loop to iterate each digit of the maximum number starting from the least significant digit.
3. Finally, sort the array on that digit using Counting sort.

Compete Source Code:

The Output of this program:

Original Input Array: [90, 106, 45, 91, 56, 40, 109, 201, 9, 100]
Array Sorted Using Radix sort: [9, 40, 45, 56, 90, 91, 100, 106, 109, 201]

Performance of Radix Sort:

If We are using Counting sort for sorting in each pass of Radix sort then the time complexity of Radix sort is O(d*(n+k)). Here O(n+k) is the time complexity of counting sort and d is the number of passes over number having d digits.

The auxiliary space requirement is (n+k). Count array takes k space and the output array of the same size as the input array is also used while sorting. The space complexity of the Radix sort is O(n+k).

You May Also Like:

That’s all about How to write a Radix sort program in Java?
If you have any feedback or suggestion please feel free to drop in below comment box.