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 \ge 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^{\sqrt{\log n} \sqrt{\log\log n + \log(1/\varepsilon)}}\)-competitive algorithm when \(m = (1+\varepsilon)n\) for any \(\varepsilon \ge \Omega(\log n / n)\). They also showed a lower bound: with \(m = \gamma n\) space, the competitive ratio of any deterministic algorithm is at least \(1/\gamma \cdot \Omega(\log n / \log\log n)\). This left an exponential gap between the upper and lower bounds for the problem.