2025/08/20 by Jubayer Nirjhor, Nirjhor, Jubayer, Nicole Wein +1
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Deterministic algorithm #FOS: Computer and information sciences #Face and Expression Recognition #Online algorithm #Sorting #Sorting algorithm #Upper and lower bounds
paper · pdf · doi:10.48550/arxiv.2508.14361
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2025/08/20 · openalex created_date 2025/10/16 · openalex updated_date 2026/07/28
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+ε) 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(√log n ⋅loglog n +log ε-1), and a lower bound of Ω(log n / loglog n) for deterministic algorithms. We obtain a deterministic algorithm with quasi-polylogarithmic cost (ε-1log n)O(log log n). Concurrent and independent work by Azar, Panigrahi, and Vardi achieves polylogarithmic cost O(ε-1log2 n).