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 "initialize" 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>C$ then $j$ is trash (because we have only initialized $C$ cells so far and $j$ isn't one of them).

If $k<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 "initialized" 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 "look" 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.

• Time cannot be smaller than space. You are cheating in some way. – Yuval Filmus Dec 16 '16 at 17:01
• Sure it can. Creating an array in size n without reseting it takes O(1). That's true for c and c++. Then you can use a very simple data structure to track which cells you've used and which are garbage – Ofer Magen Dec 16 '16 at 17:06
• I don't care much for C and C++. We usually analyze algorithms under the RAM machine model. In this model time cannot be smaller than space. I'm slightly worried that your smart array doesn't really work in $O(1)$ per access. – Yuval Filmus Dec 16 '16 at 17:08
• RAM model takes O(1) to define an array with size n (the computer only needs to define the start and end pointers). It takes O(n) to reset it to zeroes. C++ IS a ram model language that's why I brought this example – Ofer Magen Dec 16 '16 at 17:11
• @YuvalFilmus Time cannot be smaller than space true. You are cheating in some way does not follow from "$O(m+n)$ time and $O(mn)$ space": with $1 \le mn$, $xm + yn + z \in O(mn)$ - the bound on space looks needlessly lax. – greybeard May 13 '18 at 4:16

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.

• Hashtable are statistical tools and I need a deterministic solution. The use of merge sort isn't needed. You can use bucket sort because those are whole numbers in the range 1 to m and solve it in O (n+m ) – Ofer Magen Dec 19 '16 at 5:31
• The smart array however is totally deterministic – Ofer Magen Dec 19 '16 at 5:32
• You asked for faster than $O(n+m)$. $O(n \log n)$ is faster than $O(n+m)$ for some parameters -- but not for others. If you don't want to use a hashtable, use a balanced binary tree data structure, as I suggested in my answer -- that achieves the same $O(n \log n)$ running time and $O(n)$ space bounds, and does so totally deterministically. – D.W. Dec 19 '16 at 6:06