Sorting a list of strings in lexicographic order of sorted strings
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.