What is the fastest way to sort numbers lexicographically?

Question

I have $N$ sequences of numbers. None of them is longer than $10^6$. I want to sort those sequences lexicographically. For example, given sequences {1, 2, 4}, {1, 2, 3}, {2, 5, 7}, {2}, I want to have them sorted in this way - {1, 2, 3}, {1, 2, 4}, {2}, {2, 5, 7}. What is the fastest way to do this? Using quicksort and just comparing them in a normal way I can get $O(N∗K∗logN)$ but this is very slow.

Answer 1

Let $S$ be your set of sequences.

We construct increasingly refined partitions of $S$, where each class in the partition is associated to a node of a tree. Initially, the partition consists of one class (the entirety of $S$), and the tree consists of one node (the root). In your example, the initial state would look like this:

If there is a node $N$ in layer $\ell$ (where the root node is layer $0$) with more than one sequence associated to it, we create child nodes for each distinct symbol $\sigma$ occurring in the $(\ell + 1)$th position of any of the sequences, and move the sequences accordingly:

We repeat again for each of the other nodes, since they both have more than one associated sequence. Since the sequence $(2)$ does not have a second element, we leave it where it is. After both of these operations, the tree looks like this:

There is only one node remaining with more than one associated sequence. It's in the second layer, so we compare the third elements of the sequences. The tree then becomes this, at which point we terminate since all nodes have at most one associated sequence:

Now we can just do a preorder traversal of this tree, which takes time linear in the tree size.

Note that in the worst-case scenario this algorithm takes at linear time in the input size, $O(KN)$. Moreover, it is often considerably faster ($\Theta(N \log N)$ for random sequences) since it does not have to read the entire input -- in the example given, it never needs to read the symbol $7$ in the sequence $(2, 5, 7)$.

Indeed, I claim optimality of this algorithm, since it reads the minimum number of symbols required to distinguish between all of the sequences, and the time complexity is proportional to that quantity.