{"ID":2880069,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.14361","arxiv_id":"2508.14361","title":"Improved Online Sorting","abstract":"We study the online sorting problem, where $n$ real numbers arrive in an online fashion, and the algorithm must immediately place each number into an array of size $(1+\\varepsilon) n$ before seeing the next number. After all $n$ numbers are placed into the array, the cost is defined as the sum over the absolute differences of all $n-1$ pairs of adjacent numbers in the array, ignoring empty array cells. Aamand, Abrahamsen, Beretta, and Kleist introduced the problem and obtained a deterministic algorithm with cost $2^{O\\left(\\sqrt{\\log n \\cdot\\log\\log n +\\log \\varepsilon^{-1}}\\right)}$, and a lower bound of $Ω(\\log n / \\log\\log n)$ for deterministic algorithms. We obtain a deterministic algorithm with quasi-polylogarithmic cost $\\left(\\varepsilon^{-1}\\log n\\right)^{O\\left(\\log \\log n\\right)}$. Concurrent and independent work by Azar, Panigrahi, and Vardi achieves polylogarithmic cost $O(\\varepsilon^{-1}\\log^2 n)$.","short_abstract":"We study the online sorting problem, where $n$ real numbers arrive in an online fashion, and the algorithm must immediately place each number into an array of size $(1+\\varepsilon) n$ before seeing the next number. After all $n$ numbers are placed into the array, the cost is defined as the sum over the absolute differe...","url_abs":"https://arxiv.org/abs/2508.14361","url_pdf":"https://arxiv.org/pdf/2508.14361v1","authors":"[\"Jubayer Nirjhor\",\"Nicole Wein\"]","published":"2025-08-20T02:18:53Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}