# CLRS Question 8-6 Lower bound on merging sorted lists

I'm doing the CLRS Problems and there's a part I'm having trouble following.

The question is: Part a) Given 2n numbers, compute the number of possible ways to divide them into two sorted lists, each with n numbers.

Part b) Using a decision tree and your answer to part (a), show that any algorithm that correctly merges two sorted lists must perform 2n−o(n) comparisons.

Part a) makes senses to me. The first line to the solutions of part b) states any decision tree to merge two sorted lists must have at least $$2n$$ choose $$n$$ leaf nodes.

I don't follow why this is. In particular, what is each branch comparing to get to this result? And what does each leaf node represent?

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:
1. $$a_1,a_2,b_1,b_2$$ – achieved for $$A = 1,2$$ and $$B = 3,4$$.
2. $$a_1,b_1,a_2,b_2$$ – achieved for $$A = 1,3$$ and $$B = 2,4$$.
3. $$a_1,b_1,b_2,a_2$$ – achieved for $$A = 1,4$$ and $$B = 2,3$$.
4. $$b_1,a_1,a_2,b_2$$ – achieved for $$A = 2,3$$ and $$B = 1,4$$.
5. $$b_1,a_1,b_2,a_2$$ – achieved for $$A = 2,4$$ and $$B = 1,3$$.
6. $$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)$$.