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 $nH+3n$ comparisons and $1.5nH+O(n)$ moves w…