Radix Sort (MSD): Mechanism, Complexity Analysis & Interactive Visualizer

Radix Sort (MSD)

A divide-and-conquer, digit-based sorting algorithm that processes digits from Most Significant (leftmost) to Least Significant, recursively sub-sorting buckets.

How it works

Radix Sort MSD starts by sorting keys based on their leftmost digit. This groups elements into separate "buckets" (e.g. all numbers starting with 1, starting with 2, etc.). Then, each bucket containing multiple elements is sorted recursively using the next digit, until the entire array is sorted.

1. Find the maximum element in the array to identify the most significant digit position (maxExp).
2. Distribute the elements into buckets (0-9) based on the leftmost digit.
3. For each bucket that contains more than one element, recursively apply the same process using the next digit position (exp / 10).
4. Concatenate or write the sorted buckets back to the original array.

Complexity

Interactive visualization

Pseudocode

procedure radixSortMSD(A):
  n ← length(A)
  maxVal ← findMax(A)
  maxExp ← highestPowerOf10(maxVal)
  msdRecursive(A, 0, n - 1, maxExp)

procedure msdRecursive(A, lo, hi, exp):
  if lo >= hi or exp <= 0: return
  
  count ← array of size 10 initialized to 0
  output ← array of size (hi - lo + 1)
  
  for i from lo to hi:
    digit ← (A[i] / exp) % 10
    count[digit] ← count[digit] + 1
    
  countCopy ← copy of count
  for i from 1 to 9:
    count[i] ← count[i] + count[i - 1]
    
  for i from hi down to lo:
    digit ← (A[i] / exp) % 10
    pos ← count[digit] - 1
    output[pos] ← A[i]
    count[digit] ← count[digit] - 1
    
  for i from lo to hi:
    A[i] ← output[i - lo]
    
  start ← lo
  for i from 0 to 9:
    bucketSize ← countCopy[i]
    if bucketSize > 1:
      msdRecursive(A, start, start + bucketSize - 1, exp / 10)
    start ← start + bucketSize

JavaScript implementation

function radixSortMSD(arr) {
  const n = arr.length;
  if (n <= 1) return arr;

  let min = arr[0];
  let max = arr[0];
  for (let i = 1; i < n; i++) {
    if (arr[i] < min) min = arr[i];
    if (arr[i] > max) max = arr[i];
  }

  if (min < 0) {
    for (let i = 0; i < n; i++) {
      arr[i] -= min;
    }
    max -= min;
  }

  let maxExp = 1;
  while (Math.floor(max / maxExp) >= 10) {
    maxExp *= 10;
  }

  function msdSort(lo, hi, exp) {
    if (lo >= hi || exp <= 0) return;

    const count = new Array(10).fill(0);
    const aux = new Array(hi - lo + 1);

    for (let i = lo; i <= hi; i++) {
      const digit = Math.floor(arr[i] / exp) % 10;
      count[digit]++;
    }

    const countCopy = [...count];
    for (let i = 1; i < 10; i++) {
      count[i] += count[i - 1];
    }

    for (let i = hi; i >= lo; i--) {
      const digit = Math.floor(arr[i] / exp) % 10;
      const pos = count[digit] - 1;
      count[digit]--;
      aux[pos] = arr[i];
    }

    for (let i = lo; i <= hi; i++) {
      arr[i] = aux[i - lo];
    }

    let start = lo;
    for (let i = 0; i < 10; i++) {
      const bucketSize = countCopy[i];
      if (bucketSize > 1) {
        msdSort(start, start + bucketSize - 1, Math.floor(exp / 10));
      }
      start += bucketSize;
    }
  }

  msdSort(0, n - 1, maxExp);

  if (min < 0) {
    for (let i = 0; i < n; i++) {
      arr[i] += min;
    }
  }

  return arr;
}

Pros and cons

When to use it

• Lexicographical Sorting: ideal for sorting words, strings, or fixed-length binary numbers (like IP subnets).
• Very Large Datasets: when you can distribute recursive sub-sorting tasks across multiple processors.