Simple linear time algorithm for sorting strings in omega-order with applications

We present a simple linear time algorithm for the following sorting problem: Given n words $$A_1,\ldots ,A_n$$ , find a permutation $$\{\pi _1,\ldots ,\pi _n\}$$ of $$1,\ldots ,n$$ so that $$(A_{\pi _1})^\omega \le \ldots \le (A_{\pi _n})^\omega$$ , where $$(A)^\omega$$ denotes the infinitely repeating string $$AAA\ldots$$ . Let L denote the total length of the given strings. We note that the running time of our algorithm is O(L) even if the size of alphabet is beyond O(1). We also present an $$O(L+n \log n)$$ time algorithm for the restricted model where we are only allowed to compare symbols. In other words, the main result of this paper is that the time complexity of sorting $$A_1,\ldots, A_n$$ in omega-order is the same as that of sorting them in lexicographic order under all common models (bounded alphabet, unbounded alphabet, compare-based model). Our main results find applications in related problems such as rearranging and concatenating given words so that the result is lexicographically smallest or largest.