8-6 Lower bound on merging sorted lists

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

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

a. Given $2n$ numbers, compute the number of possible ways to divide them into two sorted lists, each with $n$ 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 $2n - o(n)$ comparisons.

Now we will show a slightly tighter $2n - 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 $2n - 1$ comparisons for merging two sorted lists.

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

b. Based on Exercise C.1.13,

$$ \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, \ldots, 2n - 1$ and $B = 2, 4, 6, \ldots, 2n$. By part (c), we must compare $1$ with $2$, $2$ with $3$, $3$ with $4$, and so on up until we compare $2n - 1$ with $2n$. This amounts to a total of $2n - 1$ comparisons.