Online and Fully-Dynamic Sorting
Online sorting asks how to place $n$ sequentially arriving elements in an array to minimize the sum of absolute differences between consecutive elements. Fully-dynamic sorting further extends the problem to allow both element insertions and deletions. Without recourse, these problems face strong lower bounds on the competitive ratio: $Ω(\sqrt{n})$ for online sorting and $Ω(n)$ for fully-dynamic sorting. In sharp contrast, we show that allowing only poly-logarithmic recourse yields at least exponential improvements in the competitive ratio for both problems:(1) Our main algorithmic result is a deterministic fully-dynamic sorting algorithm that is $O(\log^2 n)$-competitive and has $O(\log^4 n)$ amortized recourse per update. We complement this with a lower bound showing that any deterministic algorithm with any $O(\mathrm{polylog}(n))$ competitive ratio has amortized recourse at least $Ω(\sqrt{\log n})$.(2) For the insertion-only setting, we establish a family of approximation--recourse tradeoffs, including $O(\log\log n)$ competitive ratio with $O(\log\log n)$ amortized recourse. Given the lower bound in the fully-dynamic case, this result shows that the insertion-only problem yields exponentially better bounds than the fully-dynamic one.(3) Finally, we show that the stronger approximation-recourse tradeoff for the insertion-only case extends to the fully-dynamic setting when the array has $(1+\varepsilon)n$ space.
Authors
- Sujoy Bhore (ORCID: https://orcid.org/0000-0003-0104-1659)
- Yossi Azar (ORCID: https://orcid.org/0000-0002-5097-8993)
- Debmalya Panigrahi (ORCID: https://orcid.org/0000-0003-1799-6660)
- Or Vardi (ORCID: https://orcid.org/0009-0001-7180-7616)
- Devdan Dey
- Ian Zhang
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-16
- DOI
- https://doi.org/10.48550/arxiv.2611.20473
- Primary Topic
- Optimization and Search Problems
- Type
- preprint