Radix Sort

Stable radix sort for nonnegative integers

Comparison sorts learn order by comparing values. Radix sort instead groups values by one digit at a time, so it can be effective when keys have a bounded number of digits. This implementation uses least-significant-digit (LSD) passes in base 10 and is deliberately limited to JavaScript nonnegative safe integers.

Stable digit passes

On each pass, distribute values into ten buckets according to the current decimal digit, preserving their input order within each bucket. Then concatenate buckets in digit order. Stability matters: after sorting by the current digit, the order established by earlier, less-significant digits remains intact. After the most-significant digit is processed, the array is sorted.

The function accepts an array of nonnegative safe integers. A non-array or a non-number/non-integer element causes a TypeError; a negative or unsafe integer causes a RangeError. It does not accept negative values or fractions. The input array is never mutated, and the return value is a new array. Empty and singleton arrays return a new array with the same contents; zeros and duplicates are handled normally.

function radixSort(array) {
  if (!Array.isArray(array)) {
    throw new TypeError('Expected an array of nonnegative safe integers');
  }

  let max = 0;
  for (let i = 0; i < array.length; i += 1) {
    const value = array[i];
    if (typeof value !== 'number' || !Number.isInteger(value)) {
      throw new TypeError('Every value must be an integer number');
    }
    if (value < 0 || !Number.isSafeInteger(value)) {
      throw new RangeError('Every value must be a nonnegative safe integer');
    }
    if (value > max) max = value;
  }

  const result = array.slice();
  for (let exponent = 1; exponent <= max; ) {
    const buckets = Array.from({ length: 10 }, () => []);
    for (let i = 0; i < result.length; i += 1) {
      const digit = Math.floor(result[i] / exponent) % 10;
      buckets[digit].push(result[i]);
    }

    let outputIndex = 0;
    for (let digit = 0; digit < 10; digit += 1) {
      const bucket = buckets[digit];
      for (let i = 0; i < bucket.length; i += 1) {
        result[outputIndex] = bucket[i];
        outputIndex += 1;
      }
    }

    // Avoid multiplying beyond the highest decimal place needed for max.
    if (exponent > Math.floor(max / 10)) break;
    exponent *= 10;
  }
  return result;
}

For example, radixSort([170, 45, 75, 90, 802, 24, 2, 66]) returns [2, 24, 45, 66, 75, 90, 170, 802]. If the maximum value has w decimal digits and there are n values, the stable bucket passes take O(nw) time. The copied result and the ten buckets together use O(n + 10) extra space.

Takeaway: LSD radix sort relies on stable base-10 passes; validating the key domain and leaving the input untouched make this implementation’s contract explicit.