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 \(x_1, \ldots, x_n \in [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 \(x_1, \ldots, x_n\) is generated adversarially, the optimal cost bound for any deterministic algorithm is \(\Theta(\sqrt n)\).