Radix sort

Idea

Sort numbers digit by digit, starting from the least significant digit (LSD). Each pass is a stable sort by one digit — counting sort with only 10 possible values. Because every pass is stable, the order established by the lower digits is kept among numbers with the same higher digit. After the pass over the most significant digit the array is sorted.

Negative numbers are sorted separately by their absolute value and put in front in reverse order.

Example

Sorting [170, 45, 75, 90, 802, 24, 2, 66]. The digit of the current pass is in bold; leading zeros are shown in the last pass for clarity.

Pass	Array after the pass
input	170, 45, 75, 90, 802, 24, 2, 66
ones	170, 90, 802, 2, 24, 45, 75, 66
tens	802, 02, 24, 45, 66, 170, 75, 90
hundreds	002, 024, 045, 066, 075, 090, 170, 802

Look at 170 and 75 after the tens pass: both have 7 tens, and 170 stays before 75 because it was before it after the ones pass (0 < 5). That is why every pass must be stable.

Try it

The same example, step by step. Change the data or press Play.

Pseudocode

RADIX-SORT(A)                          // non-negative integers
  max = maximum of A
  place = 1
  while ⌊max / place⌋ > 0
    stable COUNTING-SORT of A by digit ⌊A[i] / place⌋ mod 10
    place = place × 10

Complexity

Best	Average	Worst	Memory	Stable	In place
O(d(n + b))	O(d(n + b))	O(d(n + b))	O(n + b)	yes	no

• d — number of digits of the largest absolute value, b = 10 — the base. For numbers with a bounded number of digits this is linear in n.
• Unlike counting sort, memory does not depend on the range of values: [0, 1 000 000 000] needs 10 passes, not a billion counters.
• Integers only (up to Number.MAX_SAFE_INTEGER); anything else throws a TypeError.

When to use

Many integers with a limited number of digits: IDs, timestamps, zip codes. Also for strings of equal length (sorting by characters instead of digits) and as the idea behind sorting keys made of several fields.

Usage

import { radixSort } from 'ts-ds';

const ids = [170, 45, 75, -90, 802, 24, 2, 66];
radixSort(ids); // [-90, 2, 24, 45, 66, 75, 170, 802]

API reference

Literature

• H. Hollerith's tabulating machines (1890s) sorted punched cards this way.
• CLRS, §8.3 "Radix sort".
• Sedgewick, Algorithms, §5.1 "String sorts" (LSD and MSD radix sort).