Let us consider any comparison-based algorithm for merging two ordered lists $A,B$ of length $n$, focusing on the case in which all $2n$ numbers are distinct. When the algorithm terminates, the results of the comparisons determine the merged list. Stated differently, if we describe the algorithm as a decision tree, then each leaf is labelled with the merged list, which is some permutation of the elements in $A \cup B$. Since all elements are different, each possible such permutation must be represented as some leaf.
Since the lists $A = (a_1,\ldots,a_n)$ and $B = (b_1,\ldots,b_n)$ are ordered, the permutation $\pi$ labeling each leaf must satisfy the following property: if $i < j$ then $a_i$ appears before $a_j$ and $b_i$ appears before $b_j$. This implies that $\pi$ is determined from the set of indices containing elements of $A$. There are $\binom{2n}{n}$ such possible sets, and all corresponding permutations can actually happen, as can be seen by assigning the element in the $k$th the number $k$. For example, if $n = 2$ then the possible orders are:
- $a_1,a_2,b_1,b_2$ – achieved for $A = 1,2$ and $B = 3,4$.
- $a_1,b_1,a_2,b_2$ – achieved for $A = 1,3$ and $B = 2,4$.
- $a_1,b_1,b_2,a_2$ – achieved for $A = 1,4$ and $B = 2,3$.
- $b_1,a_1,a_2,b_2$ – achieved for $A = 2,3$ and $B = 1,4$.
- $b_1,a_1,b_2,a_2$ – achieved for $A = 2,4$ and $B = 1,3$.
- $b_1,b_2,a_1,a_2$ – achieved for $A = 3,4$ and $B = 1,2$.
Therefore the decision tree must contain at least $\binom{2n}{n}$ leaves. Since it is binary (we assumed that no two elements are equal), its depth must be at least $\log_2 \binom{2n}{n}$. Stirling's approximation shows that $\binom{2n}{n} = 4^n/\Theta(\sqrt{n})$, hence $\log_2 \binom{2n}{n} = 2n - \Theta(\log n)$.
