The problem of merging two sorted lists arises frequently. We have seen a procedure for it as the subroutine MERGE\text{MERGE} in Section 2.3.1. In this problem, we will prove a lower bound of 2n12n - 1 on the worst-case number of comparisons required to merge two sorted lists, each containing nn items.

First we will show a lower bound of 2no(n)2n - o(n) comparisons by using a decision tree.

a. Given 2n2n numbers, compute the number of possible ways to divide them into two sorted lists, each with nn numbers.

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

Now we will show a slightly tighter 2n12n - 1 bound.

c. Show that if two elements are consecutive in the sorted order and from different lists, then they must be compared.

d. Use your answer to the previous part to show a lower bound of 2n12n - 1 comparisons for merging two sorted lists.

a. There are (2nn)\binom{2n}{n} ways to divide 2n2n numbers into two sorted lists, each with nn numbers.

b. Based on Exercise C.1.13,

(2nn)2hhlg(2n)!(n!)2=lg(2n!)2lg(n!)=Θ(2nlg2n)2Θ(nlgn)=Θ(2n). \begin{aligned} \binom{2n}{n} & \le 2^h \\ h & \ge \lg\frac{(2n)!}{(n!)^2} \\ & = \lg (2n!) - 2\lg (n!) \\ & = \Theta(2n\lg 2n) - 2\Theta(n\lg n) \\ & = \Theta(2n). \end{aligned}

c. We have to know the order of the two consecutive elements.

d. Let list A=1,3,5,,2n1A = 1, 3, 5, \ldots, 2n - 1 and B=2,4,6,,2nB = 2, 4, 6, \ldots, 2n. By part (c), we must compare 11 with 22, 22 with 33, 33 with 44, and so on up until we compare 2n12n - 1 with 2n2n. This amounts to a total of 2n12n - 1 comparisons.