Home/Sorting/Radix sort (LSD)
Search algorithmsCTRL K

Radix sort (LSD)

· buckets by digit, no comparisons
/sorting/radix-sort
PASS
0/ 2
one per digit, least significant first
DIGIT
—
bucket of the current value
READS
0
values bucketed
WRITES
0
values copied back
COMPARISONS
0
always zero
being bucketedwritten backdone
n = 24 · seed 7 · 102 steps
step 0 / 101
Size24
radix_sort.ts
1
function radixSort(array: number[]) {
2
  const max = Math.max(...array);
3
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
4
    const buckets: number[][] = Array.from({ length: 10 }, () => []);
5
    for (const value of array) buckets[Math.floor(value / exp) % 10].push(value);
6
    let index = 0;
7
    for (const bucket of buckets) for (const value of bucket) array[index++] = value;
8
  }
9
}
CURRENT STEP
line 2

The largest value is 98: two digits, so two passes. No comparison is ever made.

// how it works

Understanding Radix sort (LSD)

radix sort · sort by the units, then by the tens, and the tens pass keeps the units order
01

The idea

Radix sort never compares two values. It distributes the values into ten buckets by their last digit, concatenates the buckets in order, then repeats with the tens digit, the hundreds, and so on. Because each pass is stable, values that tie on the current digit keep the order the previous pass gave them, so after the last pass the array is sorted by the whole number.

The cost is one read and one write per value per digit: for d-digit keys that is O(d · n), linear in n. That beats every comparison sort's n log n bound, which does not apply because no comparison is made. The price is the buckets and the requirement that keys are integers or strings of bounded length.

02

The four stages

1
pick the digitunits first, then tens
2
bucketeach value into bucket 0–9 by that digit
3
write backbucket 0, then 1, …, keeping order inside each
4
next digituntil the largest value has no digits left
03

Complexity

best
O(d · n)d digits: two passes here
average
O(d · n)no dependence on the input order
worst
O(d · n)the same
space
O(n + b)the buckets, b = 10 here
04

Versus its siblings

OPERATIONS AT N = 1 000 · 3-DIGIT KEYS
radix (lsd)
6,000
counting
2,000
merge
8,700
quick
13,900
insertion
250,000
reads plus writes for radix and counting, comparisons for the others
05

Pseudocode

RADIXSORT(array)
  for each digit position, least significant first
    buckets[0..9] ← empty
    for each value in array, in order: append it to buckets[digit of value]
    array ← buckets[0] ++ buckets[1] ++ … ++ buckets[9]
06

When to use

Fixed-width integer keys in bulk: sorting 32-bit ids, IP addresses, dates as YYYYMMDD, suffix arrays.
GPU sorting, where the counting histogram parallelises well; it is the default sort in CUDA's Thrust for integers.
07

Pitfalls

Keys of very different lengths or floating point need preprocessing; negative integers need the sign handled as a separate pass.
A radix of 10 is for teaching; real code uses 256 or 65 536 so a 32-bit key takes 4 or 2 passes.
Each pass must be stable, or the earlier digits' order is destroyed.
08

History

Herman Hollerith's tabulating machines sorted punched cards this way in the 1890 US census, one digit column per pass, and radix sort predates the computer by half a century. Harold Seward wrote the first computer version with counting in 1954, the same paper that gave counting sort.

Back to Sorting