Radix Sort

How LSD radix sort works

Sort the array by the least-significant digit, then by the next, and so on up to the most-significant. Each pass uses a stable counting sort. After processing all digits, the array is fully sorted.

Concrete walkthrough. Sort [170, 45, 75, 90, 802, 24, 2, 66] by base 10 digits:

Initial:        [170, 45, 75, 90, 802, 24, 2, 66]
By units (1s):  [170, 90, 802, 2, 24, 45, 75, 66]   (last digits: 0, 0, 2, 2, 4, 5, 5, 6)
By tens (10s):  [802, 2, 24, 45, 66, 170, 75, 90]   (sort stable by tens: 0, 0, 2, 4, 6, 7, 7, 9)
By 100s:        [2, 24, 45, 66, 75, 90, 170, 802]   (sort stable by hundreds: 0, 0, 0, 0, 0, 0, 1, 8)

Three passes, three counting sorts. Each pass costs O(n + 10) for base 10 (n elements + 10 buckets). Three passes total: O(3 × n) = O(n). For 1M elements, ~3M operations vs ~20M for O(n log n) comparison sorts.

Byte-by-byte radix sort for 32-bit integers

For practical use on integers, base 256 (one byte per pass) is the sweet spot:

function radixSort32(arr) {
  const n = arr.length;
  let buf = new Uint32Array(n);
  let src = Uint32Array.from(arr);
  const count = new Uint32Array(256);

  for (let shift = 0; shift < 32; shift += 8) {
    count.fill(0);

    // Phase 1: count occurrences of each byte at this position
    for (let i = 0; i < n; i++) {
      count[(src[i] >>> shift) & 0xFF]++;
    }

    // Phase 2: cumulative sum
    for (let i = 1; i < 256; i++) count[i] += count[i - 1];

    // Phase 3: write to buffer in stable order (right-to-left)
    for (let i = n - 1; i >= 0; i--) {
      const byte = (src[i] >>> shift) & 0xFF;
      buf[--count[byte]] = src[i];
    }

    // Swap src and buf for next pass
    [src, buf] = [buf, src];
  }
  return Array.from(src);
}

Four passes, each O(n). For 10M random 32-bit integers, this radix sort is typically 2-5× faster than the JavaScript built-in sort() (which uses Timsort on most engines). The advantage grows for larger arrays.

Radix sort vs counting sort

	Counting sort	Radix sort
Time	O(n + k) where k = value range	O(d × (n + b)) where d = digits, b = radix
Space	O(n + k)	O(n + b)
Best for	Tiny value range (k < n)	Large value range, fixed digits
k = 1M, n = 1K	O(1M) — wasteful	O(d × 1K) — efficient
k = 10, n = 1M	O(1M) — fastest	O(d × 1M) — slower
32-bit integers	O(n + 4 × 10⁹) — impossible	O(4 × n + 4 × 256) — perfect

The core difference — counting sort is one pass over a (potentially huge) value range; radix sort is many passes over a (small) digit range. When the value range fits in memory comfortably, counting sort wins. When it doesn't, radix sort handles it.

When to use radix sort

• Sorting fixed-width integer keys. 32-bit, 64-bit, IPv4 addresses, fixed-length numeric IDs. Byte-by-byte radix sort is faster than any comparison sort.
• Sorting fixed-length strings. ISBN codes, telephone numbers, fixed-format identifiers. MSD radix sort with one digit per pass.
• Database query engines. Many embedded sorts in modern OLAP databases (DuckDB, ClickHouse) use radix sort variants when keys are integer.
• External sorting (sort-merge of huge data). Pre-radix-sort each input chunk in memory, then merge. The memory-resident phase exploits radix sort's cache friendliness.
• Suffix array construction. Specialized variants of radix sort (DC3, SAIS) compute suffix arrays in linear time, supporting full-text search and bioinformatics.

MSD radix sort and three-way radix quicksort

For variable-length string keys, LSD radix sort is wasteful — short strings get padded with implicit zero digits and processed redundantly. MSD radix sort (most-significant digit first) processes from the left, recursing into each bucket. Once a bucket has a single element (or all elements in the bucket are equal to that point), recursion stops.

Three-way radix quicksort (Bentley + Sedgewick) combines this with quicksort's partitioning. Three partitions per recursion: less-than-pivot-character, equal-to-pivot-character, greater-than. Recurse on all three; the equal-to recursion advances to the next character. Best in class for sorting general string arrays — beats both pure quicksort (no character-level optimization) and pure MSD radix (overhead per character).

Python implementation

def radix_sort_lsd(arr, base=10):
    if not arr: return arr
    max_val = max(arr)
    exp = 1
    out = list(arr)
    while max_val // exp > 0:
        out = counting_sort_by_digit(out, exp, base)
        exp *= base
    return out

def counting_sort_by_digit(arr, exp, base):
    n = len(arr)
    output = [0] * n
    count = [0] * base
    # Phase 1: count
    for x in arr:
        count[(x // exp) % base] += 1
    # Phase 2: cumulative
    for i in range(1, base):
        count[i] += count[i - 1]
    # Phase 3: stable writeback (right-to-left)
    for i in range(n - 1, -1, -1):
        digit = (arr[i] // exp) % base
        count[digit] -= 1
        output[count[digit]] = arr[i]
    return output

Common radix sort bugs

• Using an unstable sort per pass. Stability isn't optional — non-stable per-digit sorting destroys the ordering from previous passes. Always use counting sort with right-to-left writeback (or any other stable sort) per pass.
• Forgetting to handle negative numbers. Standard radix sort treats numbers as unsigned. For signed integers, either bit-cast and flip the sign bit (so positives sort above negatives), or split into negative and positive subarrays, sort each, concatenate.
• Wrong digit extraction. For LSD, the k-th pass extracts digit k from each number. Off-by-one in the shift / divisor produces a sort that "looks right" but is actually corrupted. Test with adversarial inputs (sorted, reversed, all-equal, all-different).
• Using radix sort for tiny n. For n < 100, the overhead (allocate buckets, multiple passes) makes radix sort slower than insertion sort. Hybrid algorithms switch to a comparison sort for small subarrays.
• Allocating new buckets per pass. Reuse the count array (zero-fill it) instead of allocating fresh — typical 2-3× perf improvement on hot loops.