The Magic of Non-Comparative Sorting: Radix Sort

Chris, reviewing the sorting algorithms he learned so far (Quick, Heap, Merge), discovered one commonality.

They all swap positions by "Comparing two numbers."

"Is A greater than B? Then go back."

Mathematically, it has been proven that Comparison Sorts cannot be faster than O(N log N) no matter how much you optimize the algorithm. This is the speed limit.

However, there is an algorithm that breaks this limit.

A magic that sorts data using only the property of digits (Radix) without comparing numbers at all. It is Radix Sort.

1. How Do You Sort Without Comparing?

The idea behind Radix Sort is similar to how a post office sorts mail.

A postal worker doesn't hold two letters and compare, "Which address is further back?" Instead, they simply look at the zip code and toss it into the corresponding area bin.

Radix Sort is the same.

Repeat this process up to the largest number of digits, and magically, the numbers are perfectly sorted.

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

We never compared who is bigger than whom. We just put them in and took them out according to their digits.

2. Tools for JavaScript Implementation

To implement Radix Sort, we need 3 helper functions.

// 1. Get digit (Using math tricks)
function getDigit(num, i) {
  return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}

// 2. Count digits
function digitCount(num) {
  if (num === 0) return 1;
  return Math.floor(Math.log10(Math.abs(num))) + 1;
}

// 3. Find max digits
function mostDigits(nums) {
  let maxDigits = 0;
  for (let i = 0; i < nums.length; i++) {
    maxDigits = Math.max(maxDigits, digitCount(nums[i]));
  }
  return maxDigits;
}

3. Implementing Radix Sort

function radixSort(nums) {
  let maxDigitCount = mostDigits(nums); // If the longest is 4 digits, loop 4 times

  for (let k = 0; k < maxDigitCount; k++) {
    // Create 10 empty buckets (0 ~ 9)
    let digitBuckets = Array.from({ length: 10 }, () => []);

    for (let i = 0; i < nums.length; i++) {
      // Find out the k-th digit and put it in the corresponding bucket (Push)
      let digit = getDigit(nums[i], k);
      digitBuckets[digit].push(nums[i]);
    }

    // Combine numbers in buckets in order again (Concat)
    // Same as [].concat(...digitBuckets)
    nums = [].concat(...digitBuckets);
  }

  return nums;
}

radixSort([23, 345, 5467, 12, 2345, 9852]);

4. Performance Analysis: Is it Faster than Quick Sort?

Key Takeaways

We have mastered all sorting algorithms, from the O(N^2) tortoise to the O(N log N) hare, and the O(NK) cheetah.

But in practice, what we use every day is ultimately Array.prototype.sort().

What algorithm does this built-in function actually use? And why does it sort strangely like [1, 10, 2] when sorting numbers?

🔗 References