TAOCP 5.3.2 Exercise 19
Let $M(m,n)$ denote the minimum number of comparisons required to merge two increasing sequences of lengths $m$ and $n$.
Section 5.3.2: Minimum-Comparison Merging
Exercise 19. [23] [23] Prove that the $M$ function satisfies (22).
Verified: yes
Solve time: 1m17s
Solution
Let $M(m,n)$ denote the minimum number of comparisons required to merge two increasing sequences of lengths $m$ and $n$.
Consider any optimal merging algorithm $\mathcal{A}$ that merges a sequence $A_1 < \cdots < A_m$ with $B_1 < \cdots < B_n$ using $M(m,n)$ comparisons.
Construct a transformed instance by exchanging the roles of the two input sequences. Define a new algorithm $\mathcal{A}'$ that operates on inputs of sizes $(n,m)$ by simulating $\mathcal{A}$ with the names of the sequences interchanged: every comparison $A_i : B_j$ in $\mathcal{A}$ is replaced by the comparison $B_i : A_j$ in $\mathcal{A}'$, and every branch decision is interpreted with the same logical rule after swapping the labels of the two sequences.
Each execution path of $\mathcal{A}$ on inputs $(m,n)$ corresponds bijectively to an execution path of $\mathcal{A}'$ on inputs $(n,m)$, since the ordering constraints are preserved under relabeling. The number of comparisons performed along corresponding paths is identical, since each step of $\mathcal{A}$ is reproduced exactly once in $\mathcal{A}'$ with only variable renaming.
Hence $\mathcal{A}'$ merges sequences of lengths $(n,m)$ using exactly $M(m,n)$ comparisons, which implies
$M(n,m) \le M(m,n).$
Applying the same construction in the opposite direction, starting from an optimal algorithm for $(n,m)$ and exchanging the roles of the sequences again, yields
$M(m,n) \le M(n,m).$
Combining these inequalities gives
$M(m,n) = M(n,m).$
Thus the merging function is symmetric in its arguments.
This completes the proof. ∎