= 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.
Back to article page
