Radix Sort Algorithm: Implementation in Java, an analysis of stability, parallelizability, and the Time and Space Complexities

Nickson Joram
Apr 20 · 5 min read

We have seen sorting algorithms in the earlier article. Also, in the previous article, we have discussed the Radix Sort Algorithm.

In this article, we are going to see the implementation of the algorithm, analysis of stability, parallelizability, and the Time and Space Complexities of the Radix Sorting.

How to formulate the algorithm?

radixSort(array)
d <- maximum number of digits in the largest element.
create d buckets of size 0-9.
for i <- 0 to d
sort the elements according to i th place digits using
countingSort.countingSort(array, d)
max <- find largest element among dth place elements.
initialize count array with all zeros.
for j <- 0 to size
find the total count of each unique digit in dth place of
elements and store the count at jth index in count array.
for i <- 1 to max
find the cumulative sum and store it in count array itself.
for j <- size down to 1
restore the elements to array.
decrease count of each element restored by 1.

Implement the Radix Sort Algorithm in Java

import java.util.Arrays;
public class RadixSort {
// Using counting sort to sort the elements in the basis of
significant places
public void countingSort(int array[], int size, int place) {
int[] output = new int[size + 1];
int max = array[0];
for (int i = 1; i < size; i++) {
if (array[i] > max) {
max = array[i];
}
}
int[] count = new int[max + 1];
for (int i = 0; i < max; ++i) {
count[i] = 0;
}
// Calculate count of elements
for (int i = 0; i < size; i++) {
count[(array[i] / place) % 10]++;
}
// Calculate cummulative count
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// Place the elements in sorted order
for (int i = size - 1; i >= 0; i--) {
output[count[(array[i] / place) % 10] - 1] = array[i];
count[(array[i] / place) % 10]--;
}
for (int i = 0; i < size; i++) {
array[i] = output[i];
}
}
// Function to get the largest element from an array
public int getMax(int array[], int n) {
int max = array[0];
for (int i = 1; i < n; i++) {
if (array[i] > max) {
max = array[i];
}
}
return max;
}
// Main function to implement radix sort
public void radixSort(int array[], int size) {
// Get maximum element
int max = getMax(array, size);
// Apply counting sort to sort elements based on place value.
for (int place = 1; max / place > 0; place *= 10) {
countingSort(array, size, place);
}
}
public static void main(String args[]) {
// Unsorted array
int[] data = {150, 56, 85, 60, 1202, 924, 12, 45};
int size = data.length;
RadixSort rs = new RadixSort();
rs.radixSort(data, size);
System.out.println("Sorted Array: ");
System.out.println(Arrays.toString(data));
}
}

What will be the output?

[12, 45, 56, 60, 85, 150, 924, 1202]

Time and Space Complexities

Radix sort has advantages over comparative sorting algorithms because it is a non-comparative algorithm. Radix sort will perform on n d-digit numbers where each digit can have up to b different values (since b is the base being used). In base 10, for example, a digit can be 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.

On each digit, radix sort employs a counting sort. Each pass over n d-digit numbers will take O(n+b) time, with a total of d passes. As a result, the total run time of radix sort is O(d(n+b)). When d is constant and b is not much larger than n (b=O(n)), radix sort takes linear time.

Worst Case : O(n)

Best Case : O(n)

Average Case : O(n)

If we use very large digit numbers or a large number of other bases, such as 32-bit and 64-bit numbers, it can implement in linear time, but the intermediate sort takes up a lot of space. As a result, radix sort space is inefficient. This is why this type is not used in software libraries.

Radix Sort Applications

Radix sort is implemented in

  1. DC3 algorithm (Kärkkäinen-Sanders-Burkhardt) while making a suffix array.
  2. places where there are numbers in large ranges.

Stability of Radix Sort

Radix Sort is an integer sorting algorithm that is dependent on a stable sorting subroutine. It is a sorting algorithm that does not use comparisons to sort a collection of integers. It categorizes keys based on individual digits with the same significant position and value.

Let’s unpack the formal definition and restate the basic idea:

for each digit 'k' from the least significant digit (LSD) to the most significant digit (MSD) of a number:
apply counting-sort algorithm on digit 'k' to sort the input array

Radix Sort includes Counting Sort as a subroutine. Counting Sort is a stable integer sorting algorithm. We don’t need to know how it works, but the Counting Sort is stable.

The order from previous invocations is preserved with each invocation of the Counting Sort subroutine. For example, when sorting by the tens’ place digit (second invocation), 9881 shifts downwards but remains above 9888, preserving their relative order.

Thus, Radix Sort makes use of the Counting Sort algorithm’s stability to provide linear time integer sorting.

There is another way to prove it. Just think about how this algorithm works for two numbers (say 25 and 21). Sort them! Just try!

Parallelizability of Radix Sort

Radix Sort can be Parallelized.

Let’s see about the proof in a different article. Because it will increase this article reading time. For now, just know that the Radix Sort can be Parallelized!

If you want, you can refer to the previous articles related to the Sorting Algorithms listed below.

  1. Sorting Algorithms
  2. Counting Sort Algorithm — A brief explanation with an example
  3. Counting Sort Algorithm: Implementation in Java, an analysis of stability, parallelizability, and the Time and Space Complexities
  4. Radix Sort Algorithm Explained with Examples

Hope the article can help. Share your thoughts too.

Javarevisited

Medium’s largest Java publication, followed by 10000+ programmers. Follow to join our community.

By Javarevisited

Collection of best Java articles, tutorials, courses, books, and resources from Javarevisite and its authors, Java Experts and many more.  Take a look.

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

Nickson Joram

Written by

Reading Bachelor of Science Honours in Computer Science at University of Jaffna, HND in Construction and Built Environment (Civil Engineering)

Javarevisited

A humble place to learn Java and Programming better.

Nickson Joram

Written by

Reading Bachelor of Science Honours in Computer Science at University of Jaffna, HND in Construction and Built Environment (Civil Engineering)

Javarevisited

A humble place to learn Java and Programming better.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store