Sorting a list of strings in lexicographic order of sorted strings Let $A$ be a collection of strings over the alphabet $\{0,\ldots,m-1\}$ that in total contain $n$ symbols.
Your task is to sort each of the strings internally, and then sort the resulting strings in lexicographic order. (Your algorithm doesn't have to operate this way.)
Example:
Input: 33123 15 1 0 54215 21 12
Output: 0 1 12 12 12333 12455 15

I found a way to do it in $O(m+n)$ time and $O(mn)$ space.
The space is larger than the time because I use a smart array that allows you to create an array with size $n$ and sort of giving initial values to all of the cells in $O(1)$.
I used bucket sort in order to sort each string ($O(m+n)$ time and space) and word trees in order to sort the collection $A$ itself ($O(m+n)$ time and $O(mn)$ space). but my solution is too complicated.
Does anyone have a better solution, with $O(m+n)$ time and less space, or faster than $O(m+n)$?
The solution must be deterministic so no hash maps or other statistical algorithms

My solution:
A smart array is an array of size $m$ which we can create and &quot;initialize&quot; in $O(1)$:
We create three arrays the size of $m$ without initializing any of them and we also keep a single integer variable called $C$.
The first array contains the data. The second array contains  pointers to a cell in the third array. The third array contains pointers to a cell in the second array. $C$ contains the number of cells initialed so far.
Suppose we would like to set the value of cell $i$ (suppose it is the first time we are doing it on this cell). Then we will go to cell $i$ in the first array and set it to the wanted val.
Now we go to cell $i$ in the second array and set it to point at cell $C$ at the third array. Set the  cell $C$ in the third array to point at cell $i$ in the second array. Increase $C$ by 1.
Suppose we would like to know if cell $j$ is trash (That means we have yet to set anything to it).
We would go to cell $j$ in the second array and look at the cell number (in the third array) that cell $j$ (in the second array) points to – we will call it $k$.
If $k&gt;C$ then $j$ is trash (because we have only initialized $C$ cells so far and $j$ isn't one of them).
If $k&lt;C$ we will look at what cell $k$ (in the third array) points to. If it is not $j$ then $j$ is trash. Otherwise $j$ isn't trash
That way we can know at each step if we initialized this cell and if not initialize it. So we have created and &quot;initialized&quot; an array of size $m$ in $O(1)$ time.
The main trick is not to initialize the entire array at the start but to find a way to know which cells we've initialized so far and initialize a cell only when we &quot;look&quot; at it. In the RAM model it takes $O(1)$ time to create an array of any size without initializing it.

A word tree of order m is a generalization of a TRIE. Each node contains an array of pointers to its sons. The array size is $m$.  Each node also contains a counter to say how many sets there are that are described by this node.
Because we are using smart arrays each time we add a word $A$ (a set) it only takes $O(|A|)$ time and $O(m|A|)$ space.
You can also solve this in $O(n \log n)$ time and $O(n)$ space:


First, sort each word using mergesort.  The running time of this will be at most $O(n \log n)$, and the space usage is $O(n)$.
Then, store all the words in a word trie.  The time and space for this will be $O(n)$, if you implement the word trie properly.  In particular, at each node of the trie, you should store the set of children as a hashtable (not as an array).  In this way, the storage at a node is proportional to the number of children it has, and lookup to find a child can be done in $O(1)$ time.  Thus, the running time of this stage is $O(n)$ time and $O(n)$ space.
Finally, read out all the words from the trie.  This involves taking each hashtable and sorting its contents, say using mergesort.  All of those sorting steps will take at most $O(n \log n)$ time.


The resulting data structure seems quite simple.  It's especially simple if you implement in a language that has built-in support for hashmaps (e.g., Javascript, Python).

Alternatively, you can replace the hashmap with a balanced binary tree data structure and get a similar running time.



As a general note about "smart arrays":

You can replace your use of "smart arrays" with a hashtable.  That way you will preserve the ability to do $O(1)$ (expected) time reads and writes.  In particular, instead of setting $A[i] := v$, you store value $v$ at the key $k$ (i.e., add the mapping $k \mapsto v$ to the hashtable).  When you want to read the value of $A[i]$, you instead lookup $i$ in the hashtable and return whatever you find there.  In this way, the space usage is proportional to the number of initialized entries in the "smart array", and each access takes $O(1)$ (expected) time.