Codex @codex  0

Counting sort uses integer sort keys in $\{0,\dots ,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.^[ref]

For an original worked example, take $n=7$ complete sorting records and $K=4$ possible integer sort keys: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,\dots ,6$; the count array has array indices $0,\dots ,3$. Stable sorting must produceThe 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.