Nearly Optimal Bounds for Stochastic Online Sorting

In the online sorting problem, we have an array A of n cells, and receive a stream of n items x1, . . . , xn ∈ [0, 1]. When an item arrives, we need to immediately and irrevocably place it into an empty cell. The goal is to minimize the sum of absolute differences between adjacent items, which is called the cost of the algorithm. It has been shown by Aamand, Abrahamsen, Beretta, and Kleist (SODA 2023) that when the stream x1, . . . , xn is generated adversarially, the optimal cost bound for any deterministic algorithm is Θ( √ n). In this paper, we study the stochastic version of online sorting, where the input items x1, . . . , xn are sampled uniformly at random. Despite the intuition that the stochastic version should yield much better cost bounds, the previous best algorithm for stochastic online sorting by Abrahamsen, Bercea, Beretta, Klausen and Kozma (ESA 2024) only achieves O(n 1/4 ) cost, which seems far from optimal. We show that stochastic online sorting indeed allows for much more efficient algorithms, by presenting an algorithm that achieves expected cost log n • 2 O(log * n) . We also prove a cost lower bound of Ω(log n), thus show that our algorithm is nearly optimal.