Exploit a bounded key range
Counting sort assumes integer keys in a known range, such as 0 through k−1. It counts occurrences in an array of length k instead of determining order solely through pairwise comparisons. That extra representation assumption is why its linear-style bound does not contradict the comparison-sorting lower bound. Negative integers can be offset by the minimum key, but storage depends on the span between minimum and maximum, not merely the number of distinct values. Validate this range before allocating counters or indexing them with untrusted keys.
Place labeled equal keys
For [2a,0,2b,1], the counts for keys 0, 1 and 2 are [1,1,2]. The numbers of smaller keys are [0,1,2], which provide starting output positions. Scan the input from left to right, write each record at its key’s next free position, and advance that position. The result is [0,1,2a,2b]. Unlike regenerating bare keys from their frequencies, this procedure moves complete records. It therefore retains payloads and can preserve the relative order of records sharing a key, which matters when this sort is used as one stage of a larger computation.
Define the cumulative convention
Two common conventions must not be mixed. Counts of strictly smaller keys give starting positions suitable for a left-to-right stable placement. Counts of keys less than or equal to each key give ending positions, commonly used with a right-to-left scan and a decrement before placement. Confusing these conventions causes incorrect indices or reverses duplicates. Counting, accumulating and placing require O(n+k) time. The stable output-array implementation uses O(n+k) auxiliary space. A version that only reconstructs key values has a different interface from one that must preserve full records and their order.
Check feasibility before allocating
If just one hundred keys include both zero and one billion, a counter array spanning their range can dominate all other costs. A sparse dictionary can count such keys, but producing them in sorted order then needs another ordering mechanism; this is not the same O(n+k) array algorithm. Counter overflow and overflow while computing an offset must also be considered. Counting sort is useful for small integer score ranges or bounded character classes. Its stable placement operation also provides a building block for least-significant-digit radix sorting, where retaining an earlier pass’s ordering is essential.