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

Radix Sort (LSD)

A clever sorting algorithm that processes digits from Least Significant (rightmost) to Most Significant (leftmost) using a stable sorting subroutine like Counting Sort.

How it works

Instead of comparing elements directly, Radix Sort LSD groups elements by individual digits that share the same significant position and value. Sorting from right to left maintains the relative ordering of duplicates, preserving stability.

1. Find the maximum element in the array to determine the number of digits (passes) required.
2. Start with the least significant digit (units place, exp = 1).
3. Use a stable sorting subroutine (typically Counting Sort) to sort the array elements based on the current digit.
4. Multiply the digit position by 10 (exp = exp * 10) to move to the tens place, hundreds place, etc.
5. Repeat the stable counting sort for each digit position until the most significant digit is processed.

Complexity

Interactive visualization

Pseudocode

procedure radixSortLSD(A):
  n ← length(A)
  maxVal ← findMax(A)
  
  exp ← 1
  while maxVal / exp > 0:
    countingSortForRadix(A, exp)
    exp ← exp * 10

procedure countingSortForRadix(A, exp):
  n ← length(A)
  count ← array of size 10 initialized to 0
  output ← array of size n
  
  for i from 0 to n - 1:
    digit ← (A[i] / exp) % 10
    count[digit] ← count[digit] + 1
    
  for i from 1 to 9:
    count[i] ← count[i] + count[i - 1]
    
  for i from n - 1 down to 0:
    digit ← (A[i] / exp) % 10
    pos ← count[digit] - 1
    output[pos] ← A[i]
    count[digit] ← count[digit] - 1
    
  for i from 0 to n - 1:
    A[i] ← output[i]

JavaScript implementation

function radixSortLSD(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;
  }

  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    const count = new Array(10).fill(0);
    const output = new Array(n);

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

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

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

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

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

  return arr;
}

Pros and cons

When to use it

• Large Integer Datasets: when sorting large arrays of integers where the maximum key value is known and limited.
• Fixed-Length Keys: ideal for sorting database keys, IP addresses, zip codes, or dates.