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

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.

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

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!

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.

Hope the article can help. Share your thoughts too.

## Javarevisited

### 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.

Medium sent you an email at to complete your subscription.

Written by

## Nickson Joram

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.

Written by

## Nickson Joram

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