= 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>[Theorem 11.7 and stability]{ref}
Back to article page
