What question did this study set out to answer?

The aim is to develop an efficient sorting algorithm for strings in omega-order and establish its time complexity.

April 17, 2026Open Access

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

RLRuixi LuoShenzhen University TZTaikun ZhuShenzhen University KJKai JinShenzhen University

Key Points

The aim is to develop an efficient sorting algorithm for strings in omega-order and establish its time complexity.
Develop a linear time algorithm with a running time of O(L), where L is the total string length.
Present an alternative algorithm with O(L+n log n) time complexity for a restricted model focusing on symbol comparisons.
Analyze the performance across different models (bounded/unbounded alphabet, compare-based).
Demonstrated the time complexity of omega-order sorting matches that of lexicographic sorting.
Established practical applications including rearranging strings for lexicographic optimization.

Abstract

We present a simple linear time algorithm for the following sorting problem: Given n words A₁, , Aₙ, find a permutation \ ₁, , ₙ\ of 1, , n so that (A 䃑) ^ (A 䂸) ^, where (A) ^ denotes the infinitely repeating string AAA. 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 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₁, , Aₙ 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.

Perguntar à IA

Bookmark

View Full Paper