Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 6 / d / Solution

Use counting sort with 26 counters, indexed by the character code minus the code for A. Scan the input to obtain each character's count, then emit that many copies in alphabetic order. Counting costs $O(n)$; visiting 26 counters and writing $n$ outputs costs $O(n+26)=O(n)$.

The comparison lower bound does not apply because the algorithm uses a fixed-size known alphabet and direct key indexing. It does not have to distinguish $n!$ distinct-key orders by binary comparisons; for $n>26$, distinctness is not even possible in this alphabet.