Top-Down Mergesort with Sorted Check Has Mergecost $\le (\mathcal{H}+3)n$

Abstract

We consider standard top-down recursive Mergesort, where we do a single comparison before calling merge to check if the two recursively sorted subproblems happens to already be correctly ordered. (If so, we can skip the merging step). We show for any input $A[\mathrm{0..}n)$ of elements consisting of $r$ runs (maximal increasing contiguous subranges in $A$) of respective lengths $L_1,\dots ,L_r$, the mergecost $M$ (the sum of output sizes of all merges) satisfies $M\le (\mathcal{H}+3)n$ for $\mathcal{H}={\sum }_{i=1}^r(L_i/n){\log }_2(n/L_i)$ the runlength entropy.