Nearly Tight Bounds for the Online Sorting Problem

In the online sorting problem, a sequence of n numbers in [0, 1] (including 0, 1) have to be inserted in an array of size m ≥ n so as to minimize the sum of absolute differences between pairs of numbers occupying consecutive non-empty cells. Previously, Aamand et al. (SODA 2023) gave a deterministic 2 √ log n √ log log n+log(1/ε) -competitive algorithm when m = (1 + ε)n for any ε ≥ Ω(log n/n). They also showed a lower bound: with m = γn space, the competitive ratio of any deterministic algorithm is at least 1 /γ • Ω(log n/ log log n). This left an exponential gap between the upper and lower bounds for the problem.

In this paper, we bridge this exponential gap and almost completely resolve the online sorting problem. First, we give a deterministic O(log 2 n/ε)-competitive algorithm with m = (1 + ε)n, for any ε ≥ Ω(log n/n). Next, for m = γn where γ = [O(1), O(log 2 n)], we give a deterministic O(log 2 n/γ)-competitive algorithm. In particular, this implies an O(1)-competitive algorithm with O(n log 2 n) space, which is within an O(log n•log log n) factor of the lower bound of Ω(n log n/ log log n). Combined, the two results imply a close to optimal tradeoff between space and competitive ratio for the entire range of interest: specifically, an upper bound of O(log 2 n) on the product of the competitive ratio and γ while the lower bound on this product is Ω(log n/ log log n). We also show that these results can be extended to the case when the range of the numbers is not known in advance, for an additional O(log n) factor in the competitive ratio.