Radix Sort Algorithm

Implementation in Java, an analysis of stability, parallelizability, and the Time and Space Complexities

5 min readApr 20, 2021

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

DC3 algorithm (Kärkkäinen-Sanders-Burkhardt) while making a suffix array.
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.

Hope the article can help. Share your thoughts too.