TAOCP 5.4 Exercise 3
We analyze the balanced $(P, T-P)$-way merge.
Exercise 3. [20] Show that the balanced $(P, T - P)$-way merge applied to $S$ initial runs takes $2k$ passes, when $P^k(T - P)^{k-1} < S \le P^k(T - P)^k$; and it takes $2k + 1$ passes, when $P^k(T - P)^k < S \le P^{k+1}(T - P)^k$.
Give simple formulas for (a) the exact number of passes, as a function of $S$, when $T = 2P$; and (b) the approximate number of passes, as $S \to \infty$, for general $P$ and $T$.
Verified: no
Solve time: 3m21s
Solution
We analyze the balanced $(P, T-P)$-way merge. The $T$ tapes are split into a left bank of $P$ tapes and a right bank of $T-P$ tapes. Initially $S$ runs are distributed as evenly as possible on the left bank. A pass consists of a multiway merge from one bank to the other, reading all runs and writing the merged runs onto the tapes of the target bank as evenly as possible. The first pass is a $P$-way merge (left $\to$ right), the second a $(T-P)$-way merge (right $\to$ left), the third a $P$-way merge, etc. The process stops when only one run remains.
Let $N_i$ be the number of runs after $i$ passes ($N_0 = S$). We prove by induction that for all $k \ge 0$:
- After $2k$ passes (runs on left bank): [ N_{2k} = \left\lceil \frac{S}{P^k (T-P)^k} \right\rceil. ]
- After $2k+1$ passes (runs on right bank): [ N_{2k+1} = \left\lceil \frac{S}{P^{k+1} (T-P)^k} \right\rceil. ]
Base $k=0$: $N_0 = S = \lceil S/1 \rceil$; runs are on the left bank, evenly distributed by construction.
Inductive step: Assume the formulas hold for some $k$ and the runs are evenly distributed on the current bank's tapes.
-
Pass $2k+1$ (left $\to$ right, $P$-way): The $N_{2k}$ runs are on $P$ tapes. The maximum number of runs on any tape is $\lceil N_{2k}/P \rceil$. A $P$-way merge produces exactly this many output runs (one per merge step). Using the identity $\lceil \lceil x \rceil / y \rceil = \lceil x/y \rceil$ for positive integers, [ N_{2k+1} = \left\lceil \frac{N_{2k}}{P} \right\rceil = \left\lceil \frac{\lceil S/(P^k (T-P)^k) \rceil}{P} \right\rceil = \left\lceil \frac{S}{P^{k+1} (T-P)^k} \right\rceil. ] The output runs are written on the $T-P$ tapes of the right bank as evenly as possible.
-
Pass $2k+2$ (right $\to$ left, $(T-P)$-way): Similarly, [ N_{2k+2} = \left\lceil \frac{N_{2k+1}}{T-P} \right\rceil = \left\lceil \frac{S}{P^{k+1} (T-P)^{k+1}} \right\rceil. ] The runs are again evenly distributed on the left bank.
This completes the induction.
The number of passes is the smallest $n$ such that $N_n = 1$.
-
Even case $n = 2k$: $N_{2k} = 1 \iff S \le P^k (T-P)^k$.
To ensure we did not stop earlier we need $N_{2k-1} > 1$, i.e. [ \left\lceil \frac{S}{P^k (T-P)^{k-1}} \right\rceil > 1 \iff S > P^k (T-P)^{k-1}. ] Hence $2k$ passes are required exactly when [ P^k (T-P)^{k-1} < S \le P^k (T-P)^k. ] -
Odd case $n = 2k+1$: $N_{2k+1} = 1 \iff S \le P^{k+1} (T-P)^k$.
The previous pass gave $N_{2k} > 1 \iff S > P^k (T-P)^k$.
Hence $2k+1$ passes are required exactly when [ P^k (T-P)^k < S \le P^{k+1} (T-P)^k. ]
This proves the first part of the exercise.
(a) $T = 2P$. Then $T-P = P$. The conditions become:
- $2k$ passes: $P^{2k-1} < S \le P^{2k}$.
- $2k+1$ passes: $P^{2k} < S \le P^{2k+1}$. Both are equivalent to $P^{n-1} < S \le P^n$ where $n$ is the number of passes. Therefore the exact number of passes is the smallest integer $n$ with $P^n \ge S$, i.e. [ \boxed{n = \lceil \log_P S \rceil = \lceil \log_{T/2} S \rceil}. ]
(b) Asymptotic for $S \to \infty$. For large $S$, $n$ is large and the distinction between even and odd $n$ is negligible. From the bounds, the maximum $S$ sortable in $n$ passes is roughly $P^{\lceil n/2 \rceil} (T-P)^{\lfloor n/2 \rfloor}$. Taking logarithms, [ \log S \approx \frac{n}{2} \log(P(T-P)) + O(1). ] Hence as $S \to \infty$, [ \boxed{n \sim \frac{2 \log S}{\log(P(T-P))}}. ] (The base of the logarithm is immaterial; equivalently $n = 2 \log_{P(T-P)} S + O(1)$.)
This completes the proof. ∎