Radix Sort

This page provides introduction to Radix Sort.

Overview

Radix Sort is a sorting algorithm that sorts elements by considering each digit of the elements individually. The key idea behind radix sort is to sort the elements digit by digit, starting from the least significant digit (rightmost) and moving towards the most significant digit (leftmost).

Let's sort array below, with redix sort:

$$[17, 45, 75, 90, 2, 24, 9]$$

Since radix sort sorts elements of an array digit by digit, we begin by determining the number of digits in the largest element in the array. It will be $90$ with $2$ digits.

Next, we will sort all the elements in an array by unit place digit. To do so count the number of occurrences of digits $0-9$ in the units place of the array elements, and refer to this as the counting array.

Perform a cumulative sum on the counting array, which will serve as an index for each element in the sorted array.

Sort all elements in the original array based on their units place digit, using the cumulative sum calculated in the previous step as an index. For example, if an array element has $9$ in its units digit, it will be placed at index $6$ in the sorted array because the cumulative sum of the counting array has $7$ for digit $9$.

Additionally, after placing an element in its sorted position, decrement the cumulative sum at that digit by $1$ for sorting duplicate elements.

Next, we will sort elements of an array based on their tenth place digit. After this recurssion array will be fully sorted as below:

Java

public int max(int[] arr) {
  int maxValue = Integer.MIN_VALUE;
  // calculate maxValue
  for(int i = 0; i < arr.length; i++) {
    if(maxValue < arr[i]) {
      maxValue = arr[i];
    }
  }
  return maxValue;
}

public void radixSort(int[] arr) {
  int maxValue = max(arr);
  int digitPos = 1;
  // sort by digits
  while(maxValue / digitPos > 0) {
    countingSort(arr, digitPos);
    digitPos *= 10;
  }
}


public void countingSort(int[] arr, int digitPos) {
  int[] count = new int[10];
  int[] output = new int[arr.length];

  // count occurrences of 0-9 
  for(int i = 0; i < arr.length; i++) {
    digit = (arr[i] / digitPos) % 10;
    count[digit] += 1;
  }

  // calculate cumulative sum
  for(int i = 1; i < count.length; i++) {
    count[i] += count[i - 1];
  }

  // sort based on digitPos and count array
  for(int i = arr.length - 1; i >= 0; i--) {
    digit = (arr[i] / digitPos) % 10;
    int index = count[digit] - 1
    output[index] = arr[i];
    count[digit]--;
  }

  // array copy
  for(int i = 0; i < arr.length; i++) arr[i] = output[i];
}

Complexity

Let's say there are $\text{N}$ elements in an array.

Time Complexity

Time complexity of Radix Sort is determined by the number of digits in the maximum element in the array.

$$\text{O}(\text{D} ⋅ \text{(N + B)})$$

Space Complexity

Additional space is required for buckets.

$$\text{O(N + B)}$$

Where,

$\text{B}$: Base of the number system.
$\text{D}$: Maximum number of digits in largest number.

Leetcode Problem Set