= Counting sort
{title2=$T(n,K)=O(n+K)$}
{wiki}
<Counting sort> uses <integer> <sort keys> in $\{0,\ldots,K-1\}$ directly as indices into an <array> of counts. Constant-cost counting and indexing give $O(n+K)$ <time complexity> in <Big O notation>. To retain complete <sorting records>, cumulative counts locate their <output> ranges; filling each range from its end while scanning the <input> backwards gives <stable sorting>. Emitting bare <sort keys> from counts would discard associated data. The $K$ term matters when the key range is large.<Open Data Structures: An Introduction by Pat Morin/11.2 Counting Sort and Radix Sort>[Open Data Structures: An Introduction by Pat Morin; Theorem 11.7 and stability]{ref}
For an original worked example, take $n=7$ complete <sorting records> and $K=4$ possible <integer> <sort keys>:
$$
A=\bigl((2,\mathrm A),(0,\mathrm B),(2,\mathrm C),(1,\mathrm D),(0,\mathrm E),(3,\mathrm F),(2,\mathrm G)\bigr).
$$
The letters label the associated data, and are never compared. Both <input> and <output> <array indices> start at zero, so their valid positions are $0,\ldots,6$; the count <array> has <array indices> $0,\ldots,3$. <Stable sorting> must produce
$$
B=\bigl((0,\mathrm B),(0,\mathrm E),(1,\mathrm D),(2,\mathrm A),(2,\mathrm C),(2,\mathrm G),(3,\mathrm F)\bigr).
$$
The equal-<sort key> groups retain $\mathrm B,\mathrm E$ and $\mathrm A,\mathrm C,\mathrm G$ in arrival order. <Counting sort prefix ranges> explain where those groups belong; <stable record placement in counting sort> explains how to fill them without losing that order or the complete <sorting records>.
Back to article page
