The merge-cost bound

Setting

The input consists of runs \(R_1, \ldots, R_r\) of lengths \(\ell_1, \ldots, \ell_r\), and \(n = \ell_1 + \cdots + \ell_r\). Both methods merge along a binary merge tree whose leaves are the runs; a merge costs the length of its result. With \(\operatorname{depth}(R_i)\), the number of merges that \(R_i\) takes part in, \[ M \;=\; \sum_{\text{merges } P} |P| \;=\; \sum_{i=1}^{r} \ell_i \cdot \operatorname{depth}(R_i). \] The entropy of the run lengths is \(\mathscr H = \sum_i \frac{\ell_i}{n} \lg\frac{n}{\ell_i}\), so \(n\mathscr H = \sum_i \ell_i \lg\frac{n}{\ell_i}\).

Theorem 1 (Powersort): \(M \le n(\mathscr H + 2)\)

Powers. Let \(\mu_i\) be the middle of the run \(R_i\), as a position in \([0, n]\). The boundary between \(R_{i-1}\) and \(R_i\) (\(2 \le i \le r\)) has the midpoint interval \(I_i = (\mu_{i-1}, \mu_i]\) and the power \[ P_i \;=\; \min\bigl\{\, p \ge 1 \;:\; I_i \text{ contains a multiple of } n\,2^{-p} \,\bigr\}, \qquad P_1 = P_{r+1} = 0. \]

The tree. Powersort’s merge tree is the Cartesian tree of the powers: the root is the boundary of smallest power, and the two subtrees are built in the same way from the boundaries to its left and to its right. Within a part, the smallest power is attained only once. Two multiples of \(n\,2^{-p}\) in the intervals of two of its boundaries would enclose a multiple of \(n\,2^{-(p-1)}\), which lies in the interval of a boundary in between, with a smaller power. Hence powers strictly increase along every path down the tree. The ancestors of \(R_i\) are boundaries with distinct powers, from \(1\) up to the power of its parent, which is the larger of its two neighbouring boundaries: \[ \operatorname{depth}(R_i) \;\le\; \max\{P_i, P_{i+1}\}. \]

Long intervals have small powers. An interval \((a, b]\) of length at least \(n\,2^{-p}\) contains a multiple of \(n\,2^{-p}\), wherever it lies — this is what the moving sieve shows.

The intervals are long. \(I_i\) contains the left half of \(R_i\), and \(I_{i+1}\) its right half; both are of length \(\ell_i/2\). Let \(d_i\) be the level with \(2^{-d_i} \le \frac{\ell_i/2}{n} \lt 2^{-d_i+1}\), i.e. \(d_i = \lceil \lg(n/\ell_i) + 1 \rceil\). Then \(n\,2^{-d_i} \le \ell_i/2\), so \(P_i \le d_i\) and \(P_{i+1} \le d_i\), and \[ \operatorname{depth}(R_i) \;\le\; d_i \;\lt\; \lg\frac{n}{\ell_i} + 2. \]

The sum. \(\displaystyle M = \sum_i \ell_i \operatorname{depth}(R_i) \;\le\; \sum_i \ell_i \Bigl(\lg\frac{n}{\ell_i} + 2\Bigr) = n\mathscr H + 2n.\) ∎

Theorem 2 (Peeksort): \(M \le n\mathscr H + 2n - \ell_1 - \ell_r\)

Here a single run can be deeper than \(\lg(n/\ell_i) + 2\) — see the preset “a run deeper than its share” — so the bound has to be proved for the sum. For a part \(P\) of the merge tree (a range of consecutive runs, \(|P|\) elements) let \[ E(P) \;=\; \sum_{R \subseteq P} \ell_R \lg\frac{|P|}{\ell_R}, \] let \(M(P)\) be the cost of the merges inside \(P\), and \(\ell_{\mathrm{first}}(P)\), \(\ell_{\mathrm{last}}(P)\) the lengths of its first and its last run. \(h(x) = -x\lg x - (1-x)\lg(1-x)\) is the binary entropy.

Claim. For every part \(P\): \(\;M(P) \;\le\; E(P) + 2|P| - \ell_{\mathrm{first}}(P) - \ell_{\mathrm{last}}(P)\). For the whole input, \(E = n\mathscr H\), and this is the theorem.

Proof by induction over the tree. A single run has \(M = E = 0\) and \(2\ell - \ell - \ell = 0\). Now let \(P = A[\ell..r)\) be cut at \(g\) into \(P' = A[\ell..g)\) and \(P'' = A[g..r)\), and \(x = |P'|/|P|\). The merge costs \(|P|\), and by the chain rule of entropy \[ E(P) \;=\; E(P') + E(P'') + |P|\,h(x). \] The outer runs of \(P'\) and \(P''\) are those of \(P\), plus the two runs at the cut. So the induction hypothesis for both parts gives \[ M(P) \;=\; |P| + M(P') + M(P'') \;\le\; E(P) + 2|P| - \ell_{\mathrm{first}}(P) - \ell_{\mathrm{last}}(P) \;+\; \Bigl[\, |P|\bigl(1 - h(x)\bigr) - \ell_{\mathrm{last}}(P') - \ell_{\mathrm{first}}(P'') \,\Bigr], \] and it remains to show that the bracket is at most 0: the gap \(|P|(1 - h(x))\) is paid by the two runs at the cut.

Convexity. \(\varphi(\delta) = 1 - h(\tfrac12 + \delta)\) is convex on \([0, \tfrac12]\), because \(h\) is concave, with \(\varphi(0) = 0\) and \(\varphi(\tfrac12) = 1\). So it lies below its chord, \(1 - h(\tfrac12 + \delta) \le 2\delta\). With \(\delta = |x - \tfrac12|\), since \(h\) is symmetric, \[ |P|\bigl(1 - h(x)\bigr) \;\le\; 2\delta\,|P| \;=\; |2g - \ell - r|. \]

The cut is close to the middle. Peeksort takes \(m = \ell + \lfloor (r - \ell)/2 \rfloor\), the run \(R_k = A[i..j)\) with \(i \le m \lt j\), and cuts at \(g = i\) if \(m - i \lt j - m\), else at \(g = j\). Note \(\ell + r - 2m \in \{0, 1\}\). If \(g = i\): as \(m - i \lt j - m\) are integers, \(2(m - i) \le \ell_k - 1\), so \(|2g - \ell - r| = 2(m - i) + (\ell + r - 2m) \le \ell_k\). If \(g = j\): \(2(j - m) \le \ell_k\), so \(|2g - \ell - r| = 2(j - m) - (\ell + r - 2m) \le \ell_k\). Either way \[ |P|\bigl(1 - h(x)\bigr) \;\le\; \ell_k \;\le\; \ell_{\mathrm{last}}(P') + \ell_{\mathrm{first}}(P''), \] because the cut is at an end of \(R_k\): it is the last run of \(P'\) or the first run of \(P''\). ∎

As in the animation. Unrolling the induction, \[ M \;=\; \sum_P |P| \;=\; \sum_P |P|\,h(x_P) \;+\; \sum_P |P|\bigl(1 - h(x_P)\bigr) \;=\; n\mathscr H + \sum_P \mathrm{gap}_P : \] the budgets (green) add up to \(n\mathscr H\) exactly. Each gap is at most the length of the run \(R_k\) at its cut — that run’s credit for this boundary (gold). Each boundary is cut exactly once, and each run has two boundaries, except the two outer runs, which have one each. So \(\sum_P \mathrm{gap}_P \le 2n - \ell_1 - \ell_r\).

Why not the same proof for both? The local inequality fails for Powersort. Its cuts lie next to a point of the global grid, which can be far from the middle of the current part. Powersort’s proof uses the global grid instead, and then works run by run.