Search Results

In the online sorting problem that was introduced by Aamand, Abrahamsen, Beretta and Kleist [SODA 2023], n items of real numbers arrive in an online fashion. Each item has to be placed irrevocably into an array of size n before the next item is revealed. The cost is the sum of the absolute differences between adjacent items. We study the stochastic online sorting problem where the items are sampled uniformly at random from the interval [0, 1], a problem first studied by Abrahamsen, Bercea, Klausen and Kozma [ESA 2024], who presented an algorithm achieving an expected competitive ratio of O((n log n)^{1/4}). Later Hu [SODA 2026] achieved an improved expected competitive ratio of log n ⋅ 2^O(log^* n). Hu also showed a lower bound of an expected competitive ratio of Ω(log n). In this paper, we present a simple algorithm achieving an expected competitive ratio of O(log n), thus settling the complexity. In the variant where the array has size ⌈(1 + ε) n⌉, our algorithm achieves an expected competitive ratio of O(1 + log ε^{-1}), improving the previous best known of O(1 + ε^{-1}) by Abrahamsen et al. We generalise the algorithm to higher dimensions (stochastic online Euclidean traveling salesman problem), where an expected competitive ratio of O(1) is achieved. This improves a previous competitive ratio of O(log² n) by Kalavas, Platanos and Tolias [STACS 2026].