Once upon a time I'm wrote about trie and profit and how useful it can be if use it for other purposes. link
In a word, if write a counting sorting, and use trie as associative array instead of the usual array, then can be achived O(n) complexity with not big constant. That is just add all numbers to trie and after it view all states with dfs (by that review all states in lexicographical order).
But would have to sacriface memory, because anyone vertices contains links to next stats.
P.S. To work correctly, all numbers must be completing with leading zeros.
I wonder will it be profitable to use this sorting instead of quick sort or another sort with O(n * log(n)) complexity.
P.P.S. Sorry my poor English.