If we are talking about linear in number of characters, an easy answer is building a trie and traversing it left to right. (Cache-friendly variation: https://en

If we are talking about linear in number of characters, an easy answer is building a trie and traversing it left to right. (Cache-friendly variation: https://en.wikipedia.org/wiki/Burstsort https://en.wikipedia.org/wiki/Burstsort)