Alex Zihan Xu

collaborators

2 papers

cs.DS2026

Straightforward Entropy-Sensitive Mergesort

Bill Jin, Alex Zihan Xu

In this paper, we present a stable mergesort variant, "directional mergesort", that to sort an array of $n$ elements makes no more than $n H + 3 n$ comparisons and $1.5 n H + O (n)$ moves w…

cs.DS2026

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 l g n + O (n)$ comparisons with exponentially high probability and always $O(n)…