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.

Practice

1. What is the main idea behind the Radix Sort Algorithm?

easy

A. Sort numbers by swapping adjacent elements repeatedly

B. Sort numbers by comparing each pair directly

C. Sort numbers by dividing them into two halves recursively

D. Sort numbers digit by digit starting from the least significant digit

Solution

1. Step 1: Understand Radix Sort approach

   Radix Sort sorts numbers by processing each digit separately, starting from the least significant digit (rightmost).

2. Step 2: Compare with other sorting methods

   Unlike comparison-based sorts, Radix Sort groups numbers by digits without direct comparisons between whole numbers.

3. Final Answer:

   Sort numbers digit by digit starting from the least significant digit -> Option D

4. Quick Check:

   Radix Sort = Digit by digit sorting [OK]

Hint: Radix Sort processes digits from right to left [OK]

Common Mistakes:

• Thinking Radix Sort compares whole numbers directly
• Confusing Radix Sort with quicksort or mergesort
• Assuming it sorts from most significant digit first

2. Which of the following is the correct way to initialize a bucket array for Radix Sort in JavaScript?

easy

A. const buckets = [].map(() => []);

B. const buckets = new Array(10).fill([]);

C. const buckets = Array.from({ length: 10 }, () => []);

D. const buckets = Array(10).fill(null);

Solution

1. Step 1: Understand bucket initialization

   We need 10 separate arrays (buckets) for digits 0-9. Using Array.from with a function creates independent arrays.

2. Step 2: Why other options fail

   const buckets = new Array(10).fill([]); fills with the same array reference, causing all buckets to share one array. const buckets = [].map(() => []); fails because map on empty array does nothing. const buckets = Array(10).fill(null); fills with null, not arrays.

3. Final Answer:

   const buckets = Array.from({ length: 10 }, () => []); -> Option C

4. Quick Check:

   Use Array.from with function for separate buckets [OK]

Hint: Use Array.from with arrow function for unique buckets [OK]

Common Mistakes:

• Using fill([]) creates shared references
• Using map on uninitialized array returns empty
• Filling buckets with null instead of arrays

3. What will be the output of the following JavaScript code snippet using Radix Sort on the array [170, 45, 75, 90, 802, 24, 2, 66]?

function getDigit(num, place) {
  return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}

function radixSort(arr) {
  let maxDigit = Math.floor(Math.log10(Math.max(...arr))) + 1;
  for (let k = 0; k < maxDigit; k++) {
    let buckets = Array.from({ length: 10 }, () => []);
    for (let num of arr) {
      buckets[getDigit(num, k)].push(num);
    }
    arr = [].concat(...buckets);
  }
  return arr;
}

console.log(radixSort([170, 45, 75, 90, 802, 24, 2, 66]));

medium

A. [170, 45, 75, 90, 802, 24, 2, 66]

B. [2, 24, 45, 66, 75, 90, 170, 802]

C. [802, 170, 90, 75, 66, 45, 24, 2]

D. [2, 24, 45, 66, 75, 170, 90, 802]

Solution

1. Step 1: Understand digit extraction and sorting

   The code sorts numbers by each digit from least significant (units) to most significant. After each pass, numbers are grouped by that digit.

2. Step 2: Trace sorting passes

   After sorting by units digit, then tens, then hundreds, the array becomes fully sorted ascending: [2, 24, 45, 66, 75, 90, 170, 802].

3. Final Answer:

   [2, 24, 45, 66, 75, 90, 170, 802] -> Option B

4. Quick Check:

   Radix Sort output = Sorted ascending array [OK]

Hint: Radix Sort outputs sorted array ascending [OK]

Common Mistakes:

• Confusing original array with sorted output
• Misunderstanding digit extraction order
• Assuming sorting is descending

4. Identify the bug in this Radix Sort snippet and choose the correct fix:

function radixSort(arr) {
  let maxDigit = Math.floor(Math.log10(Math.max(...arr))) + 1;
  for (let k = 0; k <= maxDigit; k++) {
    let buckets = Array.from({ length: 10 }, () => []);
    for (let num of arr) {
      buckets[Math.floor(num / Math.pow(10, k)) % 10].push(num);
    }
    arr = [].concat(...buckets);
  }
  return arr;
}

medium

A. Change loop condition to k < maxDigit instead of <= maxDigit

B. Initialize buckets with new Array(10).fill([])

C. Use Math.ceil instead of Math.floor for maxDigit

D. Remove Math.abs from digit calculation

Solution

1. Step 1: Analyze loop range for digit passes

   The loop runs from 0 to maxDigit inclusive, causing one extra pass beyond needed digits.

2. Step 2: Fix loop condition

   Changing k <= maxDigit to k < maxDigit ensures exactly maxDigit passes, avoiding unnecessary iteration.

3. Final Answer:

   Change loop condition to k < maxDigit instead of <= maxDigit -> Option A

4. Quick Check:

   Loop runs maxDigit times, not maxDigit+1 [OK]

Hint: Loop digits from 0 to less than maxDigit [OK]

Common Mistakes:

• Using <= causes extra unnecessary pass
• Initializing buckets incorrectly with shared arrays
• Changing floor to ceil breaks digit count

5. You want to use Radix Sort to sort an array containing both positive and negative integers, like [170, -45, 75, -90, 802, 24, -2, 66]. Which approach correctly adapts Radix Sort for this case?

hard

A. Separate negative and positive numbers, sort positives with Radix Sort, sort negatives by absolute value then reverse, then combine

B. Apply Radix Sort directly on all numbers including negatives without changes

C. Convert all numbers to strings and sort lexicographically

D. Use Radix Sort only on positive numbers and ignore negatives

Solution

1. Step 1: Understand Radix Sort limitation

   Radix Sort works only on non-negative integers because it sorts digits from least significant to most significant.

2. Step 2: Adapt for negatives

   Separate negatives and positives. Sort positives normally. For negatives, sort their absolute values, then reverse the result to get correct order. Finally, combine negatives (in reversed order) before positives.

3. Final Answer:

   Separate negative and positive numbers, sort positives with Radix Sort, sort negatives by absolute value then reverse, then combine -> Option A

4. Quick Check:

   Separate negatives and positives, sort separately [OK]

Hint: Sort negatives by absolute then reverse, positives normally [OK]

Common Mistakes:

• Trying to sort negatives directly with Radix Sort
• Ignoring negative numbers in sorting
• Sorting numbers as strings causing wrong order