Section 5.2.4: Sorting by Merging

Exercise 8. [M24] [M24] Let the binary representation of $N$ be $2^{e_1} + 2^{e_2} + \dots + 2^{e_t}$, where $e_1 > e_2 > \dots > e_t > 0, t > 1$. Prove that the maximum number of key comparisons performed by Algorithm L is

$$1 - 2^0 + \sum (e_i + k - 1) 2^0.$$

Verified: no
Solve time: 4m11s

---

The error in the previous solution occurs at exactly one decisive point: the computation of

$$ m_k=\left\lfloor \frac{r_k}{2}\right\rfloor $$

from the binary expansion of $N$. The derivation implicitly distributes a floor over a sum and ignores carries created by fractional parts coming from terms with $e_i=k-1$. Those carries are precisely what changes the result.

We restart from the correct structural decomposition and fix this step rigorously.

1. Cost per pass

At pass $k$, the input is a sequence of runs. As in the original argument, a two-way merge of lists of sizes $a,b$ uses exactly $a+b-1$ comparisons in the worst case. Hence, if $m_k$ merges are performed in pass $k$, then

$$ C_k = N - m_k, $$

since the total size merged is $N$, and each merge contributes one subtraction.

Thus,

$$ C(N)=\sum_{k\ge 1}(N-m_k), $$

where the sum runs until a single run remains.

2. Correct expression for the number of runs $r_k$

At the beginning of pass $k$, runs have length $2^{k-1}$. Therefore each term $2^{e_i}$ contributes:

• $2^{e_i-(k-1)}$ runs if $e_i \ge k-1$,
• $1$ run if $e_i < k-1$.

Hence

$$ r_k = \sum_{i:,e_i\ge k-1}2^{e_i-k+1} ;+;#{i : e_i < k-1}. $$

Let

$$ A_k = \sum_{i:,e_i\ge k}2^{e_i-k+1}, \qquad B_k = #{i : e_i = k-1}, \qquad C_k = #{i : e_i \le k-2}. $$

Then

$$ r_k = A_k + 2B_k + C_k. $$

3. The critical correction: computing $m_k=\lfloor r_k/2\rfloor$

We now compute:

$$ m_k = \left\lfloor \frac{A_k + 2B_k + C_k}{2} \right\rfloor = \left\lfloor \frac{A_k}{2} + B_k + \frac{C_k}{2} \right\rfloor. $$

Now observe:

• $A_k/2 = \sum_{i:e_i\ge k}2^{e_i-k}$ is an integer.
• $B_k$ is an integer.
• The only fractional contribution is $C_k/2$, where each element in $C_k$ contributes $1/2$.

Thus

$$ m_k

\sum_{i:e_i\ge k}2^{e_i-k} ;+; B_k ;+; \left\lfloor \frac{C_k}{2} \right\rfloor. $$

This is the missing correction: the term $\lfloor C_k/2\rfloor$ comes from carries between the $1/2$-contributions, which the previous solution incorrectly ignored.

4. Total comparison count

We now substitute into

$$ C(N)=\sum_k (N-m_k). $$

Split into parts:

4.1 Main geometric sum (correct as in the flawed solution)

$$ \sum_k \sum_{i:e_i\ge k}2^{e_i-k} = \sum_i (2^{e_i}-1) = N - t. $$

4.2 Middle term

$$ \sum_k B_k

\sum_k #{i : e_i = k-1} = t. $$

4.3 Carry correction term

Define

$$ D = \sum_k \left\lfloor \frac{C_k}{2} \right\rfloor. $$

This term is nonnegative and accounts exactly for the carries produced when pairing runs originating from “lower-level” exponents. It is the component missing in the incorrect proof; it is also the reason the result cannot depend only on $e_1$ and $t$.

5. Final simplification

Putting everything together:

$$ C(N) = \sum_k N

• (N - t)
• t
• D. $$

The number of passes is $e_1+1$, hence:

$$ C(N) = (e_1+1)N - (N - t) - t - D. $$

Simplifying,

$$ C(N) = e_1 N - D. $$

6. Conclusion

The correct expression for the maximum number of key comparisons in Algorithm L is:

$$ \boxed{ C(N) = e_1 N - \sum_k \left\lfloor \frac{#{i : e_i \le k-2}}{2} \right\rfloor } $$

Equivalently, in structural terms:

$$ \boxed{ C(N) = e_1 N - D } $$

where $D$ is the total number of carries created by pairing runs arising from lower-order binary components during the merging passes.

What was fixed

• The floor of a sum was no longer illegally distributed.
• Carries from fractional $1/2$-contributions were explicitly accounted for.
• The incorrect collapse to $e_1N+t$ was replaced with a correction term reflecting cross-run interactions, which the original solution omitted entirely.