Radix Sort Algorithm in DSA Javascript

Mental Model

Radix sort sorts numbers by processing digits from the smallest place to the largest, grouping numbers by each digit step by step.

Analogy: Imagine sorting mail by zip code: first by the last digit, then the second last, and so on, until all mail is sorted perfectly.

Array: [170, 45, 75, 90, 802, 24, 2, 66]
Buckets for digit 0-9:
0: []
1: []
2: []
3: []
4: []
5: []
6: []
7: []
8: []
9: []

Dry Run Walkthrough

Input: list: [170, 45, 75, 90, 802, 24, 2, 66]

Goal: Sort the list in ascending order using radix sort by sorting digits from least significant to most significant

Step 1: Sort numbers by least significant digit (ones place)

Buckets:
0: [170, 90]
2: [802, 2]
4: [24]
5: [45, 75]
6: [66]
Others: []
Reassembled array: [170, 90, 802, 2, 24, 45, 75, 66]

Why: Grouping by ones digit organizes numbers partially by their last digit

Step 2: Sort numbers by second least significant digit (tens place)

Buckets:
0: [2, 802]
2: [24]
4: [45]
6: [66]
7: [170, 75]
9: [90]
Reassembled array: [2, 802, 24, 45, 66, 170, 75, 90]

Why: Sorting by tens digit refines order based on the next digit

Step 3: Sort numbers by third least significant digit (hundreds place)

Buckets:
0: [2, 24, 45, 66, 75, 90]
1: [170]
8: [802]
Reassembled array: [2, 24, 45, 66, 75, 90, 170, 802]

Why: Sorting by hundreds digit completes the ordering for all numbers

Result:

Sorted array: [2, 24, 45, 66, 75, 90, 170, 802]

Annotated Code

DSA Javascript

class RadixSort {
  static getMax(arr) {
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] > max) max = arr[i];
    }
    return max;
  }

  static countingSort(arr, exp) {
    const output = new Array(arr.length).fill(0);
    const count = new Array(10).fill(0);

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

    // Change count[i] so it contains actual position
    for (let i = 1; i < 10; i++) {
      count[i] += count[i - 1];
    }

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

    // Copy output to arr
    for (let i = 0; i < arr.length; i++) {
      arr[i] = output[i];
    }
  }

  static radixSort(arr) {
    const max = this.getMax(arr);

    // Sort by each digit
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
      this.countingSort(arr, exp);
    }
  }
}

// Driver code
const arr = [170, 45, 75, 90, 802, 24, 2, 66];
RadixSort.radixSort(arr);
console.log(arr.join(", "));

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

Count occurrences of current digit for all numbers

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

Accumulate counts to get positions for stable sorting

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

Place elements in output array in stable order based on digit

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

Copy sorted output back to original array

for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) { this.countingSort(arr, exp); }

Repeat counting sort for each digit from least to most significant

Output

2, 24, 45, 66, 75, 90, 170, 802

Complexity Analysis

Time: O(d * (n + k)) where d is number of digits, n is number of elements, k is digit range (10); because we sort by each digit using counting sort

Space: O(n + k) for output and count arrays used in counting sort

vs Alternative: Radix sort is faster than comparison sorts like quicksort for fixed digit sizes because it sorts in linear time relative to number of digits, but uses extra space

Edge Cases

Empty array

No sorting needed, array remains empty

DSA Javascript

for (let i = 1; i < arr.length; i++) { if (arr[i] > max) max = arr[i]; }

Array with one element

Array remains unchanged as it is already sorted

DSA Javascript

for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) { this.countingSort(arr, exp); }

All elements are the same

Sorting steps run but array remains unchanged

DSA Javascript

for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) { this.countingSort(arr, exp); }

When to Use This Pattern

When you need to sort numbers with fixed digit lengths efficiently, especially non-comparison sorting, reach for radix sort because it sorts by digits stepwise.

Common Mistakes

Mistake: Not using stable sorting for each digit causes incorrect final order
Fix: Use counting sort in a stable way by iterating from right to left when placing elements

Mistake: Stopping sorting too early or too late on digits
Fix: Calculate max number and loop until all digit places are processed

Summary

Radix sort sorts numbers digit by digit from least to most significant digit.

Use it when sorting integers or fixed-length digit data efficiently without comparisons.

The key insight is sorting by each digit using a stable sort to build the final sorted array.