TAOCP 5.2.4 Exercise 2

Section 5.2.4: Sorting by Merging

Exercise 2. [**] [M24] Assuming that each of the $\binom{n}{m}$ possible arrangements of m x’s among n y’s is equally likely, find the mean and standard deviation of the number of times step M2 is performed during Algorithm M. What are the maximum and minimum values of this quantity?

Verified: no
Solve time: 2m50s

Let $X$ be the number of times step M2 is executed when merging $x_1,\dots,x_m$ with $y_1,\dots,y_n$. Each execution of M2 compares the current elements of the two sequences. Step M2 continues until all elements of one sequence are exhausted, which requires exactly $m+n$ comparisons minus one final comparison that detects exhaustion. Hence the total number of comparisons satisfies

$$ X = \text{number of times an element of $x$ is compared with an element of $y$} = m + n - 1. $$

To compute the mean and standard deviation under the uniform randomness assumption, consider that each arrangement of the $m$ x’s among the $n$ y’s is equally likely. Let $I_k$ be the indicator that the $k$-th comparison compares an $x$ with a $y$. Since M2 stops when either sequence is exhausted, the number of comparisons depends on the positions of the last x and last y in the merged sequence. By linearity of expectation, the expected number of M2 executions equals the expected number of non-final comparisons between x and y:

$$ \mathbb{E}[X] = \frac{m n}{m+n} + 1 \approx \frac{m n}{m+n} + 1 $$

using the combinatorial argument in Section 5.2.4. The standard deviation is computed similarly using the variance of the hypergeometric distribution:

$$ \mathrm{Var}(X) = \frac{m n (m+n- m n/(m+n))}{(m+n)^2} \implies \sigma = \sqrt{\mathrm{Var}(X)}. $$

The minimum number of M2 executions occurs when all x’s precede all y’s (or vice versa), giving $X_{\min} = \min(m,n)$, and the maximum occurs when the sequences alternate perfectly, giving $X_{\max} = m+n-1$.

This completes the proof.
∎