Radix Sort

in reviewThis lesson is complete and being validated before release - details may still change.

Radix sort

Loading interactive demo…

Radix sort sorts by one digit at a time, least significant first: each pass drops every bar into one of ten buckets by that digit, then lays the buckets back out in order. The digit a pass sorts by is bold in every value, and the strip under the bars is the ten buckets filling and draining. Bars parked in a bucket show translucent until they are written back. Three passes, one per digit, and the array is sorted without a single comparison. Take the tour, or press and explore. Legend:

The panel beside the stage is the real RadixSort class from the published library executing in your browser, with the current line highlighted.

The digit this pass sorts by, bold in every value label and bucket chip.
A low digit at the current place (tints run from light for 0 to strong for 9; each bucket's top edge carries its digit's tint).
A high digit at the current place.
The bar being bucketed (always the brightest bar), and the outline of the bucket receiving it.
Bars already laid back out this pass, in bucket order, and the outline of the bucket draining.
Every bar, once the whole array is sorted.

Each pass is stable, so the ones pass settles every tie the tens pass will see, and so on up: after the last digit the array is fully sorted. The work is the same on every input: shuffle, drag the bars, and the step count never moves.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Radix sort never compares two elements, so the comparison-sort lower bound of $\Omega(n \log n)$ does not apply. A pass over $n$ values in base $b$ drops each into a bucket, $O(n)$ , then walks the $b$ buckets back out, $O(n + b)$ . With $d$ passes, one per digit of the widest value:

T(n) = d \cdot O(n + b) = O(d(n + b))

Here $b = 10$ and the widest value has three digits, so $d = 3$ and the cost is linear in $n$ . Best, average and worst case are the same: the work depends only on $n$ and $d$ , never on the order of the input, which is why shuffling changes nothing on the stage. The catch is $d$ : for arbitrary $w$ -bit keys $d = w / \log_2 b$ , so radix sort wins when the keys are short relative to $\log n$ and loses when they are long. The algorithm is stable (each bucket keeps arrival order, and that is what makes the passes compose) and not in place: the buckets hold a full copy, $O(n + b)$ extra memory.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

The guard loop throws a RangeError on a negative or fractional value: digit extraction with Math.floor and % only means something for non-negative integers, so the precondition is enforced rather than documented away.
Math.max(...a, 0) makes an empty input run zero passes: the loop condition Math.floor(max / place) > 0 fails at once.
That same condition is the pass counter. place climbs 1, 10, 100 and the loop stops as soon as the widest value has no digit left at that place, so the number of passes is exactly the digit count of the maximum.
buckets is rebuilt as ten fresh empty arrays every pass with Array.from, and digit is Math.floor(a[i] / place) % base: integer division to shift the wanted digit to the ones place, then the remainder to isolate it.
The write-back is two nested for...of loops: bucket 0 to 9, then each bucket in insertion order. That inner order is the stability guarantee; a push at bucketing time and a forward walk here are all it takes.
readonly base = 10 is a field, not a parameter: the trace, the tints and the ten legend buckets all assume it, and a base of 2 or 256 would be a different lesson.

Radix sort is older than the computer. Herman Hollerith's tabulating equipment, built for the 1890 US census, read punched cards and dropped them into pockets, and the card sorters that followed it sorted one column per pass, low-order column first, so that each later pass kept the order the earlier ones had built. Harold Seward's 1954 work at MIT turned the card-room routine into an in-memory algorithm by counting the keys before placing them, the same idea behind counting sort.

1887Herman Hollerith - Develops the electric tabulating and sorting equipment for punched cards that radix sorting traces back to.source
1890US Census Office - The first census compiled with Hollerith's machines: processing drops from eight years for 1880 to six for 1890.source
1954Harold H. Seward - Develops counting sort and the first memory-efficient in-computer radix sort at MIT.source
1973Donald Knuth - The Art of Computer Programming Vol. 3, Sorting and Searching, gives radix sorting its textbook treatment beside the comparison sorts.source
1993Peter McIlroy, Keith Bostic and M. Douglas McIlroy - Publish 'Engineering Radix Sort' in Computing Systems, introducing the in-place American flag sort for strings.source

Used today

GPU sorting libraries - Radix sort has no data-dependent branches, so it maps onto thousands of parallel threads far better than a comparison sort.
Fixed-width keys at scale - IP addresses, timestamps and integer ids sort in a handful of passes regardless of how many there are.
Strings - American flag sort and burstsort apply the digit-by-digit idea to characters, beating quicksort on large string sets.

n16

digit: ones
pass: 1/3
placements: 0

radix-sort.ts

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * LSD radix sort: drop every value into one of ten buckets by its ones * digit, lay the buckets back out in order, then repeat for the tens, * the hundreds, and so on up to the widest value. Each pass is stable, * so the earlier passes settle the ties of the later ones. No value is * ever compared with another. Precondition: non-negative integers. * * Time: O(d(n + b)) for d digits in base b. Space: O(n + b) extra. */export class RadixSort implements SortAlgorithm {  readonly name = "radix-sort";  readonly base = 10;  constructor(private readonly tracer?: Tracer) {}  sort(input: readonly number[]): number[] {    const a = [...input];    const array = [...input];    for (const value of a) {    for (const value of array) {      if (!Number.isInteger(value) || value < 0) {        throw new RangeError(`radix sort needs non-negative integers, got ${value}`);      }    }    // A loop, not Math.max(...a): spreading a large array overflows the call stack.    let max = 0;    for (const value of a) if (value > max) max = value;    for (const value of array) if (value > max) max = value;    for (let place = 1; Math.floor(max / place) > 0; place *= this.base) {      const buckets: number[][] = Array.from({ length: this.base }, () => []);      // ▸ start a pass over the next digit place      this.tracer?.emit("pass", { place, array: [...a] });      this.tracer?.emit("pass", { place, array: [...array] });      for (let i = 0; i < a.length; i++) {      for (let cursor = 0; cursor < array.length; cursor++) {        const digit = Math.floor(a[i]! / place) % this.base;        const digit = Math.floor(array[cursor]! / place) % this.base;        // ▸ drop the value into the bucket its digit names        this.tracer?.emit("bucket", { digit, i, place, array: [...a] });        this.tracer?.emit("bucket", { digit, cursor, place, array: [...array] });        buckets[digit]!.push(a[i]!);        buckets[digit]!.push(array[cursor]!);      }      let k = 0;      let target = 0;      for (const bucket of buckets) {        for (const value of bucket) {          // ▸ lay the buckets back out, in order          this.tracer?.emit("write", { place, to: k, value, array: [...a] });          this.tracer?.emit("write", { place, to: target, value, array: [...array] });          a[k] = value;          array[target] = value;          k++;          target++;        }      }    }    return a;    return array;  }}

The array before sorting. Radix sort will never compare two of these bars: it reads their digits instead, ones place first.

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * LSD radix sort: drop every value into one of ten buckets by its ones * digit, lay the buckets back out in order, then repeat for the tens, * the hundreds, and so on up to the widest value. Each pass is stable, * so the earlier passes settle the ties of the later ones. No value is * ever compared with another. Precondition: non-negative integers. * * Time: O(d(n + b)) for d digits in base b. Space: O(n + b) extra. */export class RadixSort implements SortAlgorithm { readonly name = "radix-sort"; readonly base = 10; constructor(private readonly tracer?: Tracer) {} sort(input: readonly number[]): number[] { const a = [...input]; const array = [...input]; for (const value of a) { for (const value of array) { if (!Number.isInteger(value) || value < 0) { throw new RangeError(`radix sort needs non-negative integers, got ${value}`); } } // A loop, not Math.max(...a): spreading a large array overflows the call stack. let max = 0; for (const value of a) if (value > max) max = value; for (const value of array) if (value > max) max = value; for (let place = 1; Math.floor(max / place) > 0; place *= this.base) { const buckets: number[][] = Array.from({ length: this.base }, () => []); // ▸ start a pass over the next digit place this.tracer?.emit("pass", { place, array: [...a] }); this.tracer?.emit("pass", { place, array: [...array] }); for (let i = 0; i < a.length; i++) { for (let cursor = 0; cursor < array.length; cursor++) { const digit = Math.floor(a[i]! / place) % this.base; const digit = Math.floor(array[cursor]! / place) % this.base; // ▸ drop the value into the bucket its digit names this.tracer?.emit("bucket", { digit, i, place, array: [...a] }); this.tracer?.emit("bucket", { digit, cursor, place, array: [...array] }); buckets[digit]!.push(a[i]!); buckets[digit]!.push(array[cursor]!); } let k = 0; let target = 0; for (const bucket of buckets) { for (const value of bucket) { // ▸ lay the buckets back out, in order this.tracer?.emit("write", { place, to: k, value, array: [...a] }); this.tracer?.emit("write", { place, to: target, value, array: [...array] }); a[k] = value; array[target] = value; k++; target++; } } } return a; return array; }}