Sortingintermediatenon-comparisonstableinteger

Radix Sort

Sort integers digit by digit from least to most significant.

How it works

Radix Sort is a non-comparison-based sorting algorithm that processes integers one digit at a time, from the least significant digit (LSD) to the most significant. On each pass it distributes elements into ten buckets (0–9) based on the current digit, then concatenates the buckets back into the array while preserving order. Because each pass is stable, the full sort produces a correctly ordered result after processing all k digit places.

The algorithm runs in O(nk) time where k is the number of digits in the largest value, which is effectively O(n) when k is bounded by a constant (e.g. 32-bit integers). Unlike comparison-based sorts, Radix Sort never directly compares elements against each other, which allows it to sidestep the Ω(n log n) lower bound that governs comparison algorithms. This makes it particularly attractive for sorting large collections of fixed-width integers.

Radix Sort is stable — elements with equal digit values at any pass maintain their relative order, which is essential for correctness across multiple passes. It is not in-place, requiring O(n + k) auxiliary space for the bucket arrays. In practice the constant factors are small and cache performance is reasonable for large integer datasets.

Complexity

Best case

O(nk)

Average case

O(nk)

Worst case

O(nk)

Space

O(n+k)

Stable

Visualizer

Generating steps…

Where it's used in the real world

Database index builders

Sorting large integer IDs with fixed digit counts in linear time

Primary key columns are often 32- or 64-bit integers with a bounded digit count. Radix sort processes millions of row IDs in O(nk) without comparisons, making bulk index construction and re-indexing operations significantly faster than comparison-based alternatives.

Network routers — IP address sorting

Sorting IPv4 addresses by octet

IPv4 addresses are 32-bit integers naturally decomposed into four 8-bit octets. Radix sort's digit-by-digit passes map directly onto the octet structure, enabling routing tables with millions of entries to be sorted in linear time for longest-prefix-match lookups.

Suffix array construction

Used in DC3/Skew algorithm steps for string processing

The DC3/Skew algorithm for building suffix arrays applies radix sort at multiple stages to sort triples of characters in linear time. This is fundamental to efficient full-text indices, bioinformatics sequence alignment tools, and data compression (BWT/LZ-family).

Implementation

function radixSort(arr: number[]): number[] {
  const a = [...arr];
  const max = Math.max(...a);

  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    const buckets: number[][] = Array.from({ length: 10 }, () => []);

    for (const val of a) {
      buckets[Math.floor(val / exp) % 10].push(val);
    }

    let idx = 0;
    for (const bucket of buckets) {
      for (const val of bucket) {
        a[idx++] = val;
      }
    }
  }

  return a;
}

// Usage
console.log(radixSort([38, 27, 43, 3, 9, 82, 10, 55]));
// [3, 9, 10, 27, 38, 43, 55, 82]

Related algorithms

Counting SortLive

Count occurrences of each value, then reconstruct sorted output.

O(n+k)

Bucket SortLive

Distribute elements into buckets, sort each bucket, then concatenate.

O(n+k)