Near-Optimal In-Place Sorting

Abstract

We present an in-place comparison-based sorting algorithm that sorts an array of $n$ elements using $n\lg n+O(n)$ comparisons with exponentially high probability and always $O(n)$ moves. This serves as the first in-place sorting algorithm to match the fundamental $n\lg n+O(n)$ lower bound on total operations (i.e. sum of comparisons and moves). For the worst-case, we present an algorithm that makes $n\lg n+O(n{\lg }^{(t)}n)$ comparisons and $O(tn)$ data moves, where $t$ is an integer parameter satisfying $2\le t\le {\lg }^{\ast }n-1$ and ${\lg }^{(t)}n$ denotes the $t$-time iterated logarithm, improving over the previous upper bound of $n\lg n+O(n\lg \lg n)$ comparisons and $O(n)$ moves when using constant $t>2$. When $t\approx {\lg }^{\ast }n$, this yields a worst-case upper bound on total operations of $n\lg n+O(n{\lg }^{\ast }n)$. We thus achieve the ultimate goal of efficient in-place sorting via randomization whilst narrowing the gap to this goal in the worst-case. This advance involves a novel ordered set structure that supports searches in an optimal $\lg n+O(1)$ comparisons for $n$ elements. Note that both algorithms are unstable.

arXiv comment33 pages, 2 figures. Appendix starts on page 16. v2: Revised version ported to the LIPIcs template with improved presentation, added figures and stability analysis for the deterministic additional memory algorithm