---
title: Sorting in Linear Time
module: Sorting & Order Statistics
moduleNumber: 3
lessonNumber: 3
order: 303
summary: |
  The $\Omega(n\log n)$ barrier only binds algorithms that compare. By instead
  using keys as array indices we slip past it: counting sort runs in
  $\Theta(n+k)$ and is stable, radix sort layers it digit by digit, and bucket
  sort averages $\Theta(n)$ on uniform data. We see exactly when each applies.
topics: [Linear-Time Sorting]
sources:
  - book: CLRS
    ref: "§8.2–8.4 — Counting, Radix, and Bucket Sort"
  - book: Skiena
    ref: "§4 — Sorting and Searching"
  - book: Erickson
    ref: "Ch. — Sorting Beyond Comparisons"
practice:
  - title: 'Relative Sort Array'
    slug: relative-sort-array
    difficulty: Easy
  - title: 'Sort Colors'
    slug: sort-colors
    difficulty: Medium
  - title: 'H-Index'
    slug: h-index
    difficulty: Medium
  - title: 'Maximum Gap'
    slug: maximum-gap
    difficulty: Hard
---

The [previous lesson](/algorithms/sorting/sorting-lower-bounds) proved that
any sort that learns only by _comparing_ elements needs $\Omega(n\log n)$
comparisons. That proof assumes
the algorithm extracts information one comparison at a time. If instead we treat
keys as _data we can read_, using a key directly as an array index or splitting it
into digits, the decision-tree argument no longer applies, and
we can sort in **linear time**.[^erickson-beyond] The tradeoff is
generality: these algorithms need keys drawn from a small or structured universe,
not arbitrary comparables.

### How the lower bound is escaped

The $\Omega(n\log n)$ bound counts the branchings of a decision tree whose only
moves are comparisons: with $n!$ possible orderings and two outcomes per
comparison, at least $\log_2(n!) = \Theta(n\log n)$ comparisons are needed to
distinguish them. A key used _as an index_ makes a move the tree cannot: it
routes an element to one of $k$ slots in a single operation, a $k$-way branch
that no binary comparison tree models. The moment an algorithm reads a key's
value directly — rather than only its order relative to another key — the
decision-tree argument stops applying, and the floor it imposes is no longer
binding.

This works only when the key universe is
small or structured enough to index into: integers in a bounded range (counting
sort), integers split into a bounded number of digits (radix sort), or reals
whose distribution is known (bucket sort). On arbitrary
comparable objects there is nothing to index on; the only remaining move is to
compare, and the $n\log n$ bound applies again.

## Counting sort

Suppose every key is an integer in the range $\set{0, 1, \dots, k}$. **Counting
sort** never compares two elements. Instead it counts, for each value $v$, how
many keys are $\le v$; that count gives the final position of the last key
equal to $v$. Reading the input back-to-front and decrementing as we place,
we drop each element straight into its sorted slot.

```algorithm
caption: $\textsc{Counting-Sort}(A, B, k)$ — sort $A[1..n]$ with keys in $[0, k]$ into $B$
number: 1
let $C[0..k]$ be a new array
for $v \gets 0$ to $k$ do
  $C[v] \gets 0$
for $j \gets 1$ to $A.length$ do
  $C[A[j]] \gets C[A[j]] + 1$ // C[v] = count of keys = v
for $v \gets 1$ to $k$ do
  $C[v] \gets C[v] + C[v - 1]$ // C[v] = count of keys $\le v$
for $j \gets A.length$ downto $1$ do
  $B[C[A[j]]] \gets A[j]$
  $C[A[j]] \gets C[A[j]] - 1$ // next equal key goes before it
```

The first count loop tallies occurrences; the prefix-sum loop turns counts into
_ranks_ (how many keys land at or before each value); the final loop scatters
each element into its slot in the output array $B$. Walking the input from
$n$ down to $1$ is what makes the sort **stable**. Equal keys are emitted in
their original relative order, because the _last_ such key claims the _highest_
of the slots reserved for that value, and earlier ones fill in below it.

$$
% caption: Counting sort on $A=\langle 2,5,3,0,2,3,0,3\rangle$: tally counts, prefix-sum
%          into ranks, then scatter into the output $B$.
\begin{tikzpicture}[cell/.style={draw, minimum size=6.5mm, font=\small, inner sep=0pt}, lbl/.style={font=\footnotesize, anchor=east}]
  \definecolor{acc}{HTML}{2348F2}
  \node[lbl] at (-0.35,3) {input $A$};
  \foreach \v/\i in {2/0,5/1,3/2,0/3,2/4,3/5,0/6,3/7} \node[cell] at (\i*0.72,3) {\v};
  \node[font=\scriptsize,text=black] at (-0.95,1.85) {value};
  \foreach \i in {0,...,5} \node[font=\scriptsize,text=black] at (\i*0.72,1.85) {\i};
  \node[lbl] at (-0.35,1.2) {counts};
  \foreach \v/\i in {2/0,0/1,2/2,3/3,0/4,1/5} \node[cell,fill=acc!10] at (\i*0.72,1.2) {\v};
  \node[lbl] at (-0.35,0.45) {\texttt{prefix}};
  \foreach \v/\i in {2/0,2/1,4/2,7/3,7/4,8/5} \node[cell,fill=acc!18] at (\i*0.72,0.45) {\v};
  \node[lbl] at (-0.35,-0.7) {output $B$};
  \foreach \v/\i in {0/0,0/1,2/2,2/3,3/4,3/5,3/6,5/7} \node[cell,fill=acc!15,draw=acc, thick] at (\i*0.72,-0.7) {\v};
\end{tikzpicture}
$$

Trace it on $A = \langle 2,5,3,0,2,3,0,3\rangle$. The count loop tallies each
value: two $0$s, no $1$s, two $2$s, three $3$s, no $4$s, one $5$, giving
$C = \langle 2,0,2,3,0,1\rangle$. The prefix-sum loop replaces each entry with the
running total, $C = \langle 2,2,4,7,7,8\rangle$. Read this as ranks:
$C[3] = 7$ says "seven keys are $\le 3$", so the last $3$ belongs in output slot
$7$. Each value's rank now gives the exact output index of its largest copy, computed
without a single comparison between two keys.

One step of the scatter loop shows both the mechanism and the stability. Reading $A$
from the back, the last key $A[8]=3$ looks up its rank $C[3]=7$ and drops
straight into $B[7]$; we then decrement $C[3]$ to $6$, so the _next_ $3$ we meet
(an earlier one in $A$) lands in $B[6]$, just before it, preserving input order.

$$
% caption: One step of the scatter loop. The last key $A[8]=3$ reads its rank $C[3]=7$, is
%          written to $B[7]$, and then $C[3]$ is decremented to $6$ so the previous $3$
%          falls just before it — the source of stability.
\begin{tikzpicture}[
  cell/.style={draw, minimum size=6.5mm, font=\small, inner sep=0pt},
  lbl/.style={font=\footnotesize, anchor=east}]
  \definecolor{acc}{HTML}{2348F2}
  % input A, last cell highlighted
  \node[lbl] at (-0.35,2.4) {input $A$};
  \foreach \v/\i in {2/0,5/1,3/2,0/3,2/4,3/5,0/6} \node[cell] at (\i*0.72,2.4) {\v};
  \node[cell, fill=acc!15, draw=acc, very thick] (src) at (7*0.72,2.4) {3};
  \node[font=\scriptsize, text=acc, anchor=north] at (7*0.72,2.0) {$A[8]$};
  % prefix C with index labels
  \node[font=\scriptsize,text=black] at (-0.95,1.05) {value};
  \foreach \i in {0,...,5} \node[font=\scriptsize,text=black] at (\i*0.72,1.05) {\i};
  \node[lbl] at (-0.35,0.4) {\texttt{prefix} $C$};
  \foreach \v/\i in {2/0,2/1,4/2,7/3,7/4,8/5} \node[cell,fill=acc!12] at (\i*0.72,0.4) {\v};
  \node[font=\footnotesize, text=red!75!black] at (3*0.72,-0.35) {\texttt{7} $\to$ \texttt{6}};
  % output B, slot 7 (index 6) highlighted
  \node[lbl] at (-0.35,-1.6) {output $B$};
  \foreach \i in {0,...,7} \node[cell] (b\i) at (\i*0.72,-1.6) {};
  \node[cell, fill=acc!15, draw=acc, very thick] at (6*0.72,-1.6) {3};
  \foreach \i in {1,...,8} \node[font=\scriptsize, text=black] at ({(\i-1)*0.72},-2.2) {\i};
  % red leaders: read rank C[3]=7 (cell at value index 3), then write to B[7] (cell index 6)
  \draw[->, >=Stealth, red!75!black, thick] (src.south) to[out=-90,in=90] (3*0.72,0.72);
  \node[font=\scriptsize, text=red!75!black, anchor=east] at (5.2,1.45) {read $C[3]=7$};
  \draw[->, >=Stealth, red!75!black, thick] (3*0.72,0.08) to[out=-90,in=90] (6*0.72,-1.28);
  \node[font=\scriptsize, text=red!75!black, anchor=east] at (4.0,-0.95) {write to $B[7]$};
\end{tikzpicture}
$$

> **Remark (Why stability matters).** A sort is **stable** if elements with equal keys
> keep their input order. It is the property that lets us sort by one field
> without scrambling a previous ordering, and it is
> what makes radix sort correct.

**Analysis.** The loops run $\Theta(k)$, $\Theta(n)$, $\Theta(k)$, and
$\Theta(n)$ times, so counting sort is
[$\Theta(n + k)$](/algorithms/foundations/asymptotic-analysis) in both time and
space. As
long as $k = O(n)$ this is $\Theta(n)$, genuinely linear, beating the
comparison bound because no comparisons happen.[^clrs-counting] The limitation is the
_space and time in $k$_. If the keys range over, say, $32$-bit integers, then
$k \approx 4 \times 10^9$ dwarfs any realistic $n$, the count array $C$ is
enormous, and the method is impractical. Counting sort works best when the key
universe is small.

::impl{algo="counting_sort"}

## Radix sort

What if the keys are larger, say $d$-digit numbers, so that a single counting
pass is infeasible? **Radix sort** decomposes each key into $d$ digits and sorts one
digit at a time. The counterintuitive rule, known since the days of
punched-card machines, is to sort by the **least significant digit first** (LSD),
working up to the most significant.

```algorithm
caption: $\textsc{Radix-Sort}(A, d)$ — sort $d$-digit keys, least significant digit first
number: 2
for $i \gets 1$ to $d$ do
  use a stable sort to sort $A$ on digit $i$ // digit 1 = least sig.
```

The correctness rests entirely on **stability**.

> **Claim (Radix-sort correctness).** With a stable sort on each digit, after all
> $d$ passes the array is fully sorted.

> **Proof.** Induct on the number of passes: suppose after sorting on digit $i$ the
> array is correctly ordered by the low-order digits $1..i$. Now sort on digit
> $i+1$ with a _stable_ sort. Two keys differing in digit $i+1$ are ordered
> correctly by that pass. Two keys _agreeing_ in digit $i+1$ are left in their
> incoming order by stability, and that incoming order was already correct on
> digits $1..i$. So after the pass the array is correctly ordered on digits
> $1..i{+}1$, and by induction it is fully sorted after $d$ passes.[^clrs-radix]
> $\qed$

Using an unstable per-digit sort would destroy the work of every earlier pass.
This is why the inner sort must be stable, and counting sort is the natural choice.

$$
% caption: LSD radix sort over three digits; each pass stably sorts on one digit, and ties
%          keep the previous pass's order until the array is sorted.
\begin{tikzpicture}[cell/.style={draw, minimum width=10mm, minimum height=6mm, font=\small, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \h/\x in {start/0, by 1s/1.5, by 10s/3.0, {by 100s}/4.5}
    \node[font=\footnotesize] at (\x,0.7) {\h};
  \foreach \v/\r in {329/0,457/1,657/2,839/3,436/4,720/5,355/6} \node[cell] at (0,-\r*0.62) {\v};
  \foreach \v/\r in {720/0,355/1,436/2,457/3,657/4,329/5,839/6} \node[cell] at (1.5,-\r*0.62) {\v};
  \foreach \v/\r in {720/0,329/1,436/2,839/3,355/4,457/5,657/6} \node[cell] at (3.0,-\r*0.62) {\v};
  \foreach \v/\r in {329/0,355/1,436/2,457/3,657/4,720/5,839/6} \node[cell,fill=acc!15,draw=acc, thick] at (4.5,-\r*0.62) {\v};
\end{tikzpicture}
$$

A single pass shows why **stability** is required. Suppose the
array is already ordered on the low digit, and we now sort on the next one. Keys
that _tie_ on the new digit must keep their incoming order, since that order
already encodes the lower digit; only keys that _differ_ on the new digit may be
reordered.

$$
% caption: Why stability is essential. Sorting on the tens digit, keys that tie there
%          (both $3\square$) keep their incoming order, preserving the units sort; only
%          keys that differ on the tens digit cross.
\begin{tikzpicture}[
  cell/.style={draw, minimum width=11mm, minimum height=6mm, font=\small, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[font=\footnotesize, anchor=south] at (0,0.5) {after digit 1};
  \node[cell, fill=acc!12] (a0) at (0,0) {30};
  \node[cell] (a1) at (0,-0.72) {21};
  \node[cell, fill=acc!12] (a2) at (0,-1.44) {32};
  \node[cell] (a3) at (0,-2.16) {23};
  \node[font=\footnotesize, anchor=south] at (3.2,0.5) {after digit 2};
  \node[cell] (b0) at (3.2,0) {21};
  \node[cell] (b1) at (3.2,-0.72) {23};
  \node[cell, fill=acc!12] (b2) at (3.2,-1.44) {30};
  \node[cell, fill=acc!12] (b3) at (3.2,-2.16) {32};
  \draw[->, >=Stealth, red!75!black, thick] (a0.east) to (b2.west);
  \draw[->, >=Stealth] (a1.east) to (b0.west);
  \draw[->, >=Stealth, red!75!black, thick] (a2.east) to (b3.west);
  \draw[->, >=Stealth] (a3.east) to (b1.west);
  \node[font=\footnotesize, text=red!75!black, anchor=west] at (1.15,-2.95) {\texttt{30 before 32 preserved (both tens = 3)}};
\end{tikzpicture}
$$

> **Remark (MSD vs. LSD).** Sorting by the _most_ significant digit first feels more natural, since it is how we
> alphabetize, but it forces recursion into ever-finer buckets and bookkeeping
> to keep groups separate. LSD-first avoids all of that: each pass is a single
> flat stable sort over the whole array.

**Analysis.** With counting sort on each of $d$ digits, each drawn from a range
of size $k$, every pass costs $\Theta(n + k)$, for a total of

$$
\Theta\parens{d\,(n + k)}.
$$

When $d$ is a constant and $k = O(n)$, for example fixed-width integers split
into a constant number of digits in a base of size $\Theta(n)$, radix sort runs
in $\Theta(n)$. Choosing the digit size is an engineering tradeoff: larger digits
mean fewer passes ($d$ shrinks) but a larger $k$ per pass. For $b$-bit keys, the
best choice is typically digits of about $\log_2 n$ bits, so $k \approx n$ and
$d \approx b/\log_2 n$.

Consider $32$-bit keys with $n \approx 2^{16}$ elements. Splitting into
$8$-bit digits gives $d = 4$ passes over a count array of size $k = 256$; each
pass is $\Theta(n + 256) = \Theta(n)$, for $\Theta(4n)$ total. Splitting into
$16$-bit digits gives $d = 2$ passes but a count array of size $k = 65{,}536$,
comparable to $n$ itself; the total is $\Theta(2(n + n)) = \Theta(4n)$ again, but
the larger $C$ strains the cache. Halving the digit size the other way — $4$-bit
digits — doubles $d$ to $8$ passes with a tiny $k = 16$. The product
$d\,(n + k)$ is what to minimize, and the sweet spot keeps $k$ near $n$.

$$
% caption: The radix digit-size tradeoff for $32$-bit keys. Wider digits cut the pass
%          count $d$ but enlarge the per-pass count array $k$; total work $d(n+k)$ is
%          minimized when $k$ sits near $n$ (the middle rung).
\begin{tikzpicture}[font=\footnotesize, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \dig/\d/\k/\y in {4-bit/8/16/0, 8-bit/4/256/-0.9, 16-bit/2/65536/-1.8} {
    \node[anchor=east, font=\ttfamily\footnotesize] at (0,\y) {\dig};
    \node[anchor=west, font=\footnotesize] at (0.3,\y) {\texttt{d = \d\ passes}};
    \node[anchor=west, font=\footnotesize] at (3.6,\y) {\texttt{k = \k}};
  }
  \node[anchor=west, acc, font=\footnotesize] at (6.4,-0.9) {\texttt{k near n: best}};
  \draw[->, acc] (6.35,-0.9) -- (5.7,-0.9);
\end{tikzpicture}
$$

::impl{algo="radix_sort"}

## Bucket sort

Counting and radix sort exploit _integer_ keys. **Bucket sort** instead exploits
a _distributional_ assumption: that the keys are drawn (roughly) uniformly at
random from an interval, say $[0, 1)$. It scatters the $n$ keys into $n$ equal
sub-intervals, the **buckets**, sorts each bucket with a simple sort like
insertion sort, then concatenates the buckets in order.

$$
% caption: Bucket sort on $n=10$ keys in $[0,1)$. Key $x$ drops into bucket
%          $\lfloor 10x\rfloor$; each bucket is sorted and the buckets concatenated left
%          to right. Uniform keys give $\approx 1$ per bucket.
\begin{tikzpicture}[
  slot/.style={draw, minimum width=7.6mm, minimum height=6mm, font=\tiny, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i in {0,...,9} \draw (\i*0.8,0) rectangle (\i*0.8+0.8,0.6);
  \foreach \i in {0,5,10} \node[font=\tiny, text=black] at (\i*0.8,-0.28) {$\tfrac{\i}{10}$};
  \node[font=\footnotesize, anchor=east] at (-0.15,0.3) {\texttt{[0,1)}};
  \foreach \k in {0.12,0.17,0.21,0.23,0.26,0.39,0.68,0.72,0.78,0.94}
    \fill[acc] (\k*8,0.3) circle (1.1pt);
  \foreach \i in {0,...,9} \node[font=\scriptsize, anchor=north] at (\i*0.8+0.4,-0.55) {$\i$};
  \node[slot] at (1.2,-1.3) {.12};
  \node[slot] at (1.2,-1.9) {.17};
  \node[slot] at (2.0,-1.3) {.21};
  \node[slot] at (2.0,-1.9) {.23};
  \node[slot] at (2.0,-2.5) {.26};
  \node[slot] at (2.8,-1.3) {.39};
  \node[slot] at (5.2,-1.3) {.68};
  \node[slot] at (6.0,-1.3) {.72};
  \node[slot] at (6.0,-1.9) {.78};
  \node[slot] at (7.6,-1.3) {.94};
  \node[font=\scriptsize, anchor=east] at (-0.15,-1.3) {buckets};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{Bucket-Sort}(A)$ — sort $n$ keys drawn uniformly from $[0, 1)$
number: 3
$n \gets A.length$
let $B[0..n-1]$ be an array of empty lists
for $i \gets 1$ to $n$ do
  insert $A[i]$ into list $B[\,\floor{n \cdot A[i]}\,]$ // bucket by value
for $i \gets 0$ to $n - 1$ do
  sort list $B[i]$ with insertion sort
concatenate $B[0], B[1], \dots, B[n-1]$ in order
```

Scattering is $\Theta(n)$, and concatenation is $\Theta(n)$. The only variable
cost is sorting the buckets. If the input is spread uniformly, each bucket holds
about one element on average, so the insertion sorts cost $O(1)$ each in
expectation.[^clrs-bucket]

**Analysis.** Let $n_i = |B[i]|$. Insertion sort on bucket $i$ costs
$O(n_i^2)$, so the expected total bucket-sorting cost is
$\sum_i \mathbb{E}[O(n_i^2)] = \sum_i O(\mathbb{E}[n_i^2])$. Each key lands in
bucket $i$ independently with probability $1/n$, so $n_i$ is Binomial$(n, 1/n)$,
which has

$$
\mathbb{E}[n_i^2] = \Var(n_i) + \mathbb{E}[n_i]^2
= \parens{1 - \tfrac1n} + 1^2 = 2 - \tfrac1n < 2.
$$

Summing over the $n$ buckets gives $\sum_i O(\mathbb{E}[n_i^2]) = O(n)$, so the
total expected running time is

$$
\Theta(n) + n \cdot O(1) = \Theta(n).
$$

This is an **average-case** result: it assumes the inputs are uniformly
distributed. Adversarial input, with every key landing in the same bucket,
degrades bucket sort to the $\Theta(n^2)$ of a single insertion sort. Bucket sort
is the right tool when you know your data is spread evenly (or can cheaply map it
so), as with fractional parts of well-mixed values.

### A worked bucket sort

Take the $n = 10$ keys
$A = \langle 0.78,\, 0.17,\, 0.39,\, 0.26,\, 0.72,\, 0.94,\, 0.21,\, 0.12,\, 0.23,\, 0.68\rangle$,
uniform-looking values in $[0, 1)$. Each key $x$ lands in bucket
$\floor{10x}$, so $0.78 \to B[7]$, $0.17 \to B[1]$, $0.39 \to B[3]$, and so on.
Scattering costs one pass:

| bucket $i$ | keys placed (in arrival order) |
| --- | --- |
| $0$ | — |
| $1$ | $0.17,\ 0.12$ |
| $2$ | $0.26,\ 0.21,\ 0.23$ |
| $3$ | $0.39$ |
| $6$ | $0.68$ |
| $7$ | $0.78,\ 0.72$ |
| $9$ | $0.94$ |

Buckets $0$, $4$, $5$, and $8$ stay empty. Insertion sort now orders each
bucket's short list — bucket $1$ becomes $\langle 0.12, 0.17\rangle$, bucket $2$
becomes $\langle 0.21, 0.23, 0.26\rangle$, bucket $7$ becomes
$\langle 0.72, 0.78\rangle$ — and reading the buckets left to right concatenates
them into the sorted output. No bucket held more than three keys, so every
insertion sort was $O(1)$ work, and the whole sort touched each key a constant
number of times.

$$
% caption: Bucket sort on the $10$ keys. Each key scatters to bucket $\lfloor 10x\rfloor$,
%          buckets are insertion-sorted in place (most hold $0$ or $1$ key), then read left
%          to right into the sorted run.
\begin{tikzpicture}[
  slot/.style={draw, minimum width=8mm, minimum height=6mm, font=\scriptsize, inner sep=0pt},
  empty/.style={draw, minimum width=8mm, minimum height=6mm, font=\scriptsize, inner sep=0pt, fill=black!5},
  lbl/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  % bucket index labels
  \foreach \i in {0,...,9} \node[lbl] at (\i*0.95,0.55) {\i};
  % bucket contents, sorted, stacked
  \node[empty] at (0,0) {};
  \node[slot, fill=acc!12] at (0.95,0) {.12};   \node[slot, fill=acc!12] at (0.95,-0.62) {.17};
  \node[slot, fill=acc!12] at (1.9,0) {.21};    \node[slot, fill=acc!12] at (1.9,-0.62) {.23};  \node[slot, fill=acc!12] at (1.9,-1.24) {.26};
  \node[slot, fill=acc!12] at (2.85,0) {.39};
  \node[empty] at (3.8,0) {};
  \node[empty] at (4.75,0) {};
  \node[slot, fill=acc!12] at (5.7,0) {.68};
  \node[slot, fill=acc!12] at (6.65,0) {.72};   \node[slot, fill=acc!12] at (6.65,-0.62) {.78};
  \node[empty] at (7.6,0) {};
  \node[slot, fill=acc!12] at (8.55,0) {.94};
  % sorted output
  \node[lbl, anchor=east] at (-0.55,-2.3) {sorted};
  \foreach \v/\i in {.12/0,.17/1,.21/2,.23/3,.26/4,.39/5,.68/6,.72/7,.78/8,.94/9}
    \node[slot, fill=acc!18, draw=acc, thick] at (\i*0.95,-2.3) {\v};
  \draw[->, >=Stealth, acc] (4.3,-1.65) -- (4.3,-1.95);
  \node[lbl, text=acc, anchor=west] at (4.5,-1.75) {concatenate};
\end{tikzpicture}
$$

::impl{algo="bucket_sort"}

## Choosing among them

None of these linear-time sorts is a drop-in replacement for a comparison sort
like [mergesort](/algorithms/divide-and-conquer/mergesort) or
[heapsort](/algorithms/sorting/heaps-and-heapsort). Each rests on a structural
assumption about the keys, so the choice comes down to matching the algorithm to
what you know about your data.[^skiena-sort]

| Algorithm | Assumption on keys | Time | Stable? | Extra space |
| --- | --- | --- | --- | --- |
| **Counting sort** | integers in a small range $[0, k]$ | $\Theta(n + k)$ | yes | $\Theta(n + k)$ |
| **Radix sort** | $d$ digits, each in a small range | $\Theta(d(n + k))$ | yes | $\Theta(n + k)$ |
| **Bucket sort** | reals spread uniformly over an interval | $\Theta(n)$ expected | yes | $\Theta(n)$ |

Practical guidance:

- Use **counting sort** when keys are integers over a range comparable to
  $n$ (grades, small ages, byte values). It is also the standard stable subsort
  _inside_ radix sort.
- Use **radix sort** for fixed-width keys with a larger range, such as
  $32$- or $64$-bit integers or fixed-length strings, where a single counting
  pass would need an impossibly large count array.
- Use **bucket sort** when keys are real numbers believed to be uniformly
  (or near-uniformly) distributed, and linear _expected_ time suffices.

These methods beat $\Omega(n\log n)$ precisely because
they are **not** comparison sorts: they
_compute_ with the keys rather than comparing them. On arbitrary comparable objects with no
exploitable integer or distributional structure, the linear-time guarantee is
gone, and a comparison sort with its $n\log n$ bound is the only option.

## Radix sort in practice

The textbook radix sort scatters into $k$ separate output lists per pass, paying
$\Theta(n + k)$ auxiliary space. In production that copying and the poor cache
behavior of scattered writes are the bottleneck, and two refinements address them.

**MSD radix, in place: American flag sort.** Sorting most-significant digit first
lets a radix sort partition the array _in place_, the way quicksort does, rather
than into external buckets. **American flag sort** (McIlroy, Bostic, and McIlroy,
1993) makes two passes over the array per digit: the first counts how many keys
fall in each of the $k$ digit values, turning the counts into bucket boundaries;
the second permutes elements into place by following a cycle of swaps, so each key
is moved directly to its bucket with no auxiliary array. It then recurses on each
bucket for the next digit. The in-place permutation trades counting sort's
$\Theta(n)$ scratch space for a swap-heavy inner loop, and because it is MSD it can
stop early on distinguishing prefixes — the standard choice for sorting large
string sets where keys share long common prefixes.

**Adaptive bucketing: spreadsort.** Bucket sort's fragility is its fixed uniform
partition; real data is rarely uniform. **Spreadsort** (Ross, 2002; shipped in the
Boost C++ libraries) is a hybrid that inspects the actual range of the keys, sizes
its buckets to that range rather than assuming $[0,1)$, and recursively spreads or
falls back to a comparison sort when a bucket is small enough that partitioning no
longer pays. It interpolates between radix sort's digit-splitting and quicksort's
divide-and-conquer, achieving close to linear time on real numeric data without
bucket sort's uniform-distribution assumption or radix sort's fixed digit width.

**Where linear sorts actually run.** Radix
sort is the standard high-throughput sort on **GPUs**: a GPU has thousands of
lanes but suffers from the branch divergence of a comparison sort's data-dependent
control flow, whereas a radix pass is a fixed sequence of counts and scatters that
maps cleanly onto parallel prefix-sums (Merrill and Grimshaw, 2011). **Column-store
databases** likewise radix-sort fixed-width integer and date columns, and
**MapReduce**-style systems partition keys by a radix-like hash to route them to
reducers. The common pattern: when the keys
have exploitable structure, computing with them beats comparing them, and the
advantage is largest on wide parallel hardware and
data too large to shuffle randomly.[^skiena-sort]

## Takeaways

- The $\Omega(n\log n)$ bound binds only **comparison sorts**; using keys as
  array indices or digit sequences sidesteps it entirely.
- **Counting sort** ranks keys by prefix-summing their counts: $\Theta(n + k)$,
  **stable**, linear when $k = O(n)$ but impractical when $k$ is large.
- **Radix sort** stably sorts digit by digit, **least significant first**;
  stability is what preserves earlier passes, giving $\Theta(d(n+k))$.
- **Bucket sort** scatters uniform keys into $n$ buckets and sorts each;
  expected $\Theta(n)$, but $\Theta(n^2)$ if the distribution is adversarial.
- Each linear sort trades generality for a **structural assumption** on the
  keys, so choose by what you actually know about your data.

[^erickson-beyond]: **Erickson**, _Algorithms_, Ch. — Sorting Beyond Comparisons — treating keys as readable data sidesteps the decision-tree argument and permits linear-time sorting.
[^clrs-counting]: **CLRS**, §8.2 — Counting Sort — counting sort runs in $\Theta(n + k)$, is stable, and is linear when $k = O(n)$.
[^clrs-radix]: **CLRS**, §8.3 — Radix Sort — sorting least-significant digit first with a stable subsort yields a correct sort in $\Theta(d(n+k))$.
[^clrs-bucket]: **CLRS**, §8.4 — Bucket Sort — scattering uniformly distributed keys into $n$ buckets gives expected $\Theta(n)$ running time.
[^skiena-sort]: **Skiena**, _The Algorithm Design Manual_, §4 — Sorting and Searching — choosing the right sort by matching the algorithm to the structure of the keys.