Radix Sort

Sorting

avgO(d·(n + b))worstO(d·(n + b))spaceO(n + b)

main

out

digit

The largest value 97 has 2 digits

1 / 88

Code

function radixSort(a: number[]) {  const max = Math.max(...a);  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {    const count = new Array(10).fill(0);    for (const x of a) count[Math.floor(x / exp) % 10]++;    for (let d = 1; d < 10; d++) count[d] += count[d - 1];    const out = new Array(a.length);    for (let i = a.length - 1; i >= 0; i--) {      out[--count[Math.floor(a[i] / exp) % 10]] = a[i];    }    for (let i = 0; i < a.length; i++) a[i] = out[i];  }  return a;}

procedure radixSort(A)    ▷ LSD, base 10  max ← maximum(A)  for exp ← 1, 10, 100, … while ⌊max / exp⌋ > 0 do    count ← ten zeros    for each x in A do count[digit(x, exp)] ← count[digit(x, exp)] + 1    for d ← 1 to 9 do count[d] ← count[d] + count[d − 1]    out ← new array of size n    for i ← n − 1 down to 0 do    ▷ stable counting sort by this digit      count[digit(A[i], exp)] ← count[digit(A[i], exp)] − 1; out[count[digit(A[i], exp)]] ← A[i]    end for    copy out back into A  end for  return Aend procedure

Variables

max=97

Counters

passes: 0
writes: 0

Size20

Distribution

Custom values2 to 150 whole numbers, each 1 to 999

seed 4

How it works

Sorts by one decimal digit at a time, least significant first, using a stable counting sort for each digit. Because each pass is stable, ties keep the order the earlier digits produced, and after the last digit the whole array is sorted.

Complexity

Best: O(d·(n + b))
Average: O(d·(n + b))
Worst: O(d·(n + b))
Space: O(n + b)
Stable: Yes
In place: No

Radix Sort

How it works

Complexity

Search algorithms