Şahin Arslan

Posted on Oct 19 • Originally published at sahinarslan.tech

A Voyage through Algorithms using Javascript - Radix Sort

#javascript #algorithms #webdev #computerscience

What is Radix Sort?

Radix Sort is a clever non-comparison based sorting algorithm that sorts integers by processing individual digits. Think of it like opening a baggage lock with multiple dials. You align the digits one dial at a time. First, you sort all numbers based on the rightmost digit (the ones place), then move to the next digit (tens place), and continue until every dial is aligned. By the end, all the numbers are perfectly ordered without ever directly comparing them.

Unlike comparison-based algorithms like Bubble Sort, Insertion Sort, and Merge Sort, Radix Sort doesn't compare numbers directly. Instead, it leverages Counting Sort as a subroutine to sort numbers digit by digit. The time complexity is O(d × (n + k)), where d is the number of digits, n is the number of elements, and k is the range of digit values (0-9 for decimal numbers).

Radix Sort shines when dealing with integers, especially when they have a fixed number of digits or when the range is large but the number of digits is reasonable. It's not a general-purpose sort like Merge Sort, but when the conditions align, it can outperform even the most optimized comparison-based algorithms.

How Radix Sort Works

Radix Sort operates through a systematic, digit-by-digit approach:

Find the maximum number: Determine how many digits we need to process by finding the largest number in the array.
Start from the least significant digit (LSD): Begin with the rightmost digit (ones place).
Use stable sorting: Sort the entire array based on the current digit using a stable algorithm (typically Counting Sort).
Move to the next digit: Shift one position left (tens, hundreds, thousands, etc.).
Repeat until done: Continue until you've processed all digits of the maximum number.

This approach utilizes the stability requirement in a smart way. When you sort by the ones place first, then the tens place, the stability plays the key role: numbers with the same tens digit remain in the order established by their ones digit. This cascading effect builds up the final sorted result.

Here's a visualization to make the concept clearer:

Implementing Radix Sort in JavaScript

Let's take a look at the implementation of Radix Sort in JavaScript, with detailed comments explaining each part:

function radixSort(arr) {
  if (arr.length === 0) return arr;

  // STEP 1: Find the maximum number to determine how many digits we need to process
  // This tells us how many times we need to run our digit-by-digit sorting
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }

  // STEP 2: Process each digit position, starting from the least significant (rightmost)
  // exp represents which digit we're looking at: 1 for ones, 10 for tens, 100 for hundreds, etc.
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    // Use counting sort to sort based on the current digit
    arr = countingSortByDigit(arr, exp);
  }

  return arr;
}

function countingSortByDigit(arr, exp) {
  // This is counting sort modified to sort by a specific digit position
  const output = new Array(arr.length);
  const count = new Array(10);

  // Initialize count array to zeros manually
  for (let i = 0; i < 10; i++) {
    count[i] = 0;
  }

  // STEP 1: Count occurrences of each digit (0-9) at the current position
  for (let i = 0; i < arr.length; i++) {
    // Extract the digit at position 'exp': (num / exp) % 10
    // Example: For 342 with exp=10, we get (342/10)%10 = 34%10 = 4 (the tens digit)
    const digit = Math.floor(arr[i] / exp) % 10;
    count[digit]++;
  }

  // STEP 2: Transform counts to cumulative positions
  // This tells us where each digit group should END in the output array
  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }

  // STEP 3: Build the output array by placing elements in their sorted positions
  // Process backwards to maintain stability - must have for Radix sort!
  for (let i = arr.length - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    const position = count[digit] - 1;
    output[position] = arr[i];  // Place the entire number
    count[digit]--;
  }

  return output;
}

// Example usage:
const numbers = [170, 45, 75, 90, 802, 24, 2, 66];
console.log("Original:", numbers);
console.log("Sorted:", radixSort(numbers));

/*
Output:
Original: [170, 45, 75, 90, 802, 24, 2, 66]
Sorted: [2, 24, 45, 66, 75, 90, 170, 802]
*/

Key Implementation Details for Radix Sort

1. The Exponential Loop Magic

for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10)

The loop continues while there are still digits to process. When max / exp becomes less than 1, we've processed all digits. For example, with max = 802:

exp = 1: 802 / 1 = 802 (process ones place)
exp = 10: 802 / 10 = 80.2 (process tens place)
exp = 100: 802 / 100 = 8.02 (process hundreds place)
exp = 1000: 802 / 1000 = 0.802 → Stop!

2. The Digit Extraction Trick

const digit = Math.floor(arr[i] / exp) % 10;

This formula extracts any digit from a number:

arr[i] / exp shifts the desired digit to the ones place
Math.floor() removes everything to the right
% 10 isolates just that single digit

Examples:

For 342 with exp = 1: Math.floor(342 / 1) % 10 = 342 % 10 = 2 (ones digit)
For 342 with exp = 10: Math.floor(342 / 10) % 10 = 34 % 10 = 4 (tens digit)
For 342 with exp = 100: Math.floor(342 / 100) % 10 = 3 % 10 = 3 (hundreds digit)

3. Why Stability is Non-Negotiable

Radix Sort absolutely requires a stable sorting algorithm for each digit pass. Here's why:

// Original array: [13, 12]
// After sorting by ones place (3 vs 2): [12, 13] ✓
// After sorting by tens place (1 vs 1): 
//   - With stability: [12, 13] ✓ (preserves ones-place order)
//   - Without stability: [13, 12] ✗ (might swap unnecessarily)

Without stability, the carefully established order from previous digit passes would be destroyed. That's why we use the stable variant of Counting Sort as our subroutine.

4. The Backwards Pass Trick

for (let i = arr.length - 1; i >= 0; i--)

Processing the array backwards when placing elements into the output is what guarantees stability in our Counting Sort implementation. This is critical for Radix Sort to work correctly.

5. Handling Zero Values

The algorithm naturally handles zeros because:

Math.floor(0 / exp) % 10 = 0 for any exp
Zeros get counted in count[0]
They're placed at the beginning of the output (where they belong!)

Radix Sort's Stability Chain Pattern

The magic of Radix Sort comes from its stability chain. Let's follow through an example to see this in action:

// Original: [170, 45, 75, 90, 802, 24, 2, 66]

// After sorting by ONES place (exp = 1):
// [170, 90, 802, 2, 24, 45, 75, 66]
// Buckets: 
// 0 → [170, 90]
// 2 → [802, 2]
// 4 → [24]
// 5 → [45, 75]
// 6 → [66]

// After sorting by TENS place (exp = 10):
// [802, 2, 24, 45, 66, 170, 75, 90]
// Buckets:
// 0 → [802, 2]
// 2 → [24]
// 4 → [45]
// 6 → [66]
// 7 → [170, 75, 90]
// Notice: **170 stays before 75, which stays before 90** — stability preserved!

// After sorting by HUNDREDS place (exp = 100):
// [2, 24, 45, 66, 75, 90, 170, 802]
// Buckets:
// 0 → [2, 24, 45, 66, 75, 90]
// 1 → [170]
// 8 → [802]
// The previous ones and tens order is preserved within each hundred’s bucket!

Time and Space Complexity Analysis

Radix Sort's performance characteristics are:

Time Complexity: O(d × (n + k)) in all cases

d = number of digits in the maximum number
n = number of elements in the array
k = range of digit values (10 for decimal numbers)
We run Counting Sort d times, and each Counting Sort pass takes O(n + k)

In practice, for decimal numbers (k = 10), this simplifies to O(d × n).

Space Complexity: O(n + k)

O(n) for the output array in each Counting Sort pass
O(k) for the count array (10 for decimal digits)
Total: O(n + 10) = O(n) in practice

The d factor is the critical trade-off: Radix Sort's efficiency depends entirely on how many digits you're processing. Let's look at real numbers:

Example 1: Sorting 1,000,000 elements

32-bit integers (max value ~4 billion) have at most 10 digits
Radix Sort: 10 passes through 1 million elements = 10 million operations
Merge Sort: needs roughly 20 million comparisons (n log n where log of 1 million ≈ 20)
Radix Sort wins: fewer total operations

Example 2: Sorting 1,000 elements

Same 32-bit integers with 10 digits
Radix Sort: 10 passes through 1,000 elements = 10,000 operations
Merge Sort: needs roughly 10,000 comparisons (n log n where log of 1,000 ≈ 10)
Close comparison: similar operation counts

Example 3: Sorting 1,000 elements with huge numbers

128-bit integers (max 39 digits)
Radix Sort: 39 passes through 1,000 elements = 39,000 operations
Merge Sort: still roughly 10,000 comparisons
Merge Sort wins: way fewer operations needed

What to look for:

Small d, large dataset: Radix Sort shines (millions of phone numbers, IP addresses)
Large d, small dataset: Comparison sorts are simpler and faster
Rule of thumb: If your maximum value has more than 15-20 digits, reconsider Radix Sort

The larger your dataset, the more Radix Sort's fixed number of passes pays off. The more digits in your numbers, the more those passes cost you.

Is Radix Sort Stable?

Yes, Radix Sort is a stable sorting algorithm, but only when implemented with a stable subroutine like Counting Sort.

The stability of Radix Sort is inherited from its subroutine:

Each digit pass must maintain the relative order of elements with the same digit
This cascades through all digit positions
The final result preserves the original order of equal elements

If you tried using an unstable sort (like a naive Quick Sort) for the digit passes, Radix Sort would break. The algorithm fundamentally depends on stability to build up the correct final order.

Advantages and Disadvantages of Radix Sort

Advantages:

Linear time complexity when d is small: O(d × n) beats O(n log n)
Stable sorting algorithm
Predictable performance - no worst-case degradation
Excellent for fixed-length integer keys
Can be parallelized for each digit position

Disadvantages:

Only works for integers (or data that can be represented as integers)
Performance degrades when d (number of digits) is large
Requires extra space: O(n) for output arrays
More complex to implement than simple comparison sorts
Not cache-friendly due to scattered memory access patterns

When to Choose Radix Sort

Radix Sort excels in specific scenarios but has clear limitations. Here's when to consider it:

Perfect for:

Fixed-length integers: Social security numbers, zip codes, product IDs
Large datasets with small digit counts: Millions of 32-bit integers (d=10)
Uniform integer distributions: Data where numbers have similar digit lengths
Stable sorting requirements: When order preservation matters
Known digit ranges: When you can control or predict the maximum value

Avoid when:

Variable-length data: Strings of very different lengths, arbitrary-precision numbers
Large d values: Sorting 128-bit integers or cryptographic hashes
Non-integer data: Floating-point numbers (without conversion), complex objects
Small datasets: The overhead isn't worth it for 100 elements
Memory constraints: If you can't afford O(n) extra space

The golden rule: Radix Sort is brilliant when d << log n, meaning the number of digits is much smaller than the logarithm of the array size. If you're sorting a million integers (log n ≈ 20) with 6 digits each, Radix Sort wins. If you're sorting a thousand 50-digit numbers, comparison sorts are better.

Radix Sort vs Counting Sort: When to Use Which?

Since Radix Sort uses Counting Sort internally, you might wonder when to use each:

Use Counting Sort when:

Values are in a small, known range (e.g., 0-100)
The range k is not much larger than n
You're sorting primitive integers directly

Use Radix Sort when:

Values have multiple digits/positions to process
The range is large but digit count is small (e.g., 32-bit integers)
You want to avoid the range limitation of Counting Sort

Example:

// Counting Sort is better:
[23, 45, 12, 89, 67, 34]  // Range: 12-89 (78 values)

// Radix Sort is better:
[123456, 789012, 345678, 901234]  // Range: huge, but only 6 digits

Real-World Applications

Radix Sort shines in problems where data naturally has fixed-length integer keys:

Data Processing: Sorting IP addresses, MAC addresses, social security numbers, zip codes, phone numbers

Computer Graphics: Sorting pixels by color channels, z-buffer sorting for 3D rendering

Database Systems: Integer key indexing, parallel sorting in distributed systems

Network Routing: Sorting packets by priority or destination codes

Scientific Computing: Sorting particle positions, grid coordinates in simulations

Handling Negative Numbers

The implementation above works only for non-negative integers. To handle negative numbers, you have two approaches with different trade-offs:

Offset Approach: Best when the range is reasonable

Shifts all numbers to be non-negative by adding the absolute value of the minimum
Simpler logic, single sort pass
Risk: Can cause integer overflow if your numbers are near the maximum integer limit
Choose this when: Your numbers are well within safe integer ranges

Split and Merge: Best for extreme values

Separates negatives and positives, sorts independently, then combines
No overflow risk since we're working with absolute values
Slightly more operations (two separate sorts)
Choose this when: You're dealing with very large numbers or want guaranteed safety

Option 1: Offset Approach

function radixSort(arr) {
  if (arr.length === 0) return arr;

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

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

  return arr;
}

function countingSortByDigit(arr, exp) {
  const output = new Array(arr.length);
  const count = new Array(10);

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

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

  return output;
}

function radixSortWithNegatives(arr) {
  if (arr.length === 0) return arr;

  // Find min to offset all values to non-negative
  let min = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < min) min = arr[i];
  }

  let offset = min < 0 ? -min : 0;

  // Offset all values
  let offsetArr = new Array(arr.length);
  for (let i = 0; i < arr.length; i++) {
    offsetArr[i] = arr[i] + offset;
  }

  // Sort the offset array
  let sorted = radixSort(offsetArr);

  // Remove offset
  let result = new Array(sorted.length);
  for (let i = 0; i < sorted.length; i++) {
    result[i] = sorted[i] - offset;
  }

  return result;
}

// Example usage:
const mixedNumbers = [170, -45, 75, -90, 802, 24, -2, 66];
console.log("Sorted:", radixSortWithNegatives(mixedNumbers));
// Output: [-90, -45, -2, 24, 66, 75, 170, 802]

Option 2: Split and Merge

function radixSort(arr) {
  if (arr.length === 0) return arr;

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

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

  return arr;
}

function countingSortByDigit(arr, exp) {
  const output = new Array(arr.length);
  const count = new Array(10);

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

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

  return output;
}

function radixSortWithNegatives(arr) {
  // Separate negatives and positives
  let negatives = [];
  let positives = [];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < 0) {
      negatives.push(-arr[i]);  // Store as positive
    } else {
      positives.push(arr[i]);
    }
  }

  // Sort both groups
  negatives = radixSort(negatives);
  positives = radixSort(positives);

  // Reverse negatives and negate them back
  let result = new Array(negatives.length + positives.length);
  let index = 0;

  for (let i = negatives.length - 1; i >= 0; i--) {
    result[index] = -negatives[i];
    index++;
  }

  for (let i = 0; i < positives.length; i++) {
    result[index] = positives[i];
    index++;
  }

  return result;
}

// Example usage:
const mixedNumbers = [170, -45, 75, -90, 802, 24, -2, 66];
console.log("Sorted:", radixSortWithNegatives(mixedNumbers));
// Output: [-90, -45, -2, 24, 66, 75, 170, 802]

Bottom line: For most everyday use cases, go with the split and merge approach. It's more intuitive (you can see it sorting negatives and positives separately), safer (no overflow worries), and the performance difference is negligible. Only choose offset if you're really trying to squeeze out every bit of performance and you're certain your values are safe.

Conclusion

Radix Sort reminds us that sometimes the best way to solve a problem is to break it into smaller, identical subproblems.

Radix Sort isn't a general-purpose solution, but understanding it gives further inspiration about the algorithm design. It shows how leveraging data structure (multiple digits) and algorithmic properties (stability) in a creative way can unlock performance gains that seem impossible at first glance.

When you're sorting integers and the conditions align, do remember about the Radix Sort. It might just be the fastest tool in your algorithmic toolbox for that specific problem.

DEV Community