Sorting a list of strings in lexicographic order of sorted strings

Question

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.

Answer 1

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.

Answer 2

You can sort a set $S$ of strings over an integer alphabet $\{0,1,\dots,\sigma-1\}$ of size $\sigma$ using a trie in $O(d\sigma)$ time and space, where $d$ is the distinguishing prefix of $S$.

Here's a solution not using hash tables.

Let $d_s$ be length of the shortest prefix of the string $s \in S$ that distinguishes it from the other strings in $S$. The distinguishing prefix of $S$ is defined as $d = \sum_{s\in S}d_s$.

The algorithm to solve the problem uses a divide & conquer approach, it's a RadixSort that start from the most significant digit (char).

1) Create $\sigma$ buckets $0,1,\dots,\sigma-1$

2) Process the strings character-by-character from their beginning and distribute them into $\sigma$ buckets using CountingSort in $O(1)$ time.

3) Repeat the process on buckets containing more than one element using the next character to sort them.

4) Concatenate the groups left to right to get the ordered sequence.

This algorithm generates a $\sigma$-ary trie, in which every node is a $\sigma$ sized array and the strings are stored in the leaves.

Here is an example.

Let $\sigma$ be $5$ and $S=\{410,013,042,111,001,444\}$.

The following is the trie generated by the algorithm:

Each string $s$ spells out a path of size $O(d_s)$ before the node pointing to $s$ is created. Each node of those paths takes $O(\sigma)$ space and $O(\sigma)$ time to be allocated.