Treating keys as indexed categories
If keys are integers from zero through R−1, an array can count how many records have each key. One scan updates the corresponding frequency slots. This uses the representation and range of keys rather than only pairwise comparison.
Records can also carry names, timestamps or other payloads. Frequencies alone can reproduce a sorted list of plain integer values, but sorting complete records requires distributing each original record into output positions without losing its associated data.
References: [1]
Cumulative counts determine output regions
Cumulative frequencies give the number of records preceding each category and thus its starting output position. A second input scan places each record in its category’s next free slot and advances that position. Categories occupy disjoint, ordered regions.
Distributing in input order preserves order within each equal-key category, producing a stable version. Implementations often reuse the count array for advancing positions, so these mutated offsets should not later be mistaken for unchanged original frequencies.
References: [1]
The key range is part of the cost
A typical stable implementation for n records and R possible keys takes O(n+R) time and additional space. A huge sparse key range can dominate these costs even when there are few records.
This does not contradict comparison-sorting lower bounds because direct key indexing provides extra information. Character encodings, offsets for negative integers and category mappings must match the intended order; an arbitrary mapping does not automatically implement linguistic collation.