Near-Optimal In-Place Sorting

Alex Zihan Xu, Stephen Jing Chick

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)…