The problem of merging two sorted lists arises frequently. We have seen a procedure for it as the subroutine in Section 2.3.1. In this problem, we will prove a lower bound of on the worst-case number of comparisons required to merge two sorted lists, each containing items.
First we will show a lower bound of comparisons by using a decision tree.
a. Given numbers, compute the number of possible ways to divide them into two sorted lists, each with 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 comparisons.
Now we will show a slightly tighter 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 comparisons for merging two sorted lists.
a. There are ways to divide numbers into two sorted lists, each with numbers.
b. Based on Exercise C.1.13,
c. We have to know the order of the two consecutive elements.
d. Let list and . By part (c), we must compare with , with , with , and so on up until we compare with . This amounts to a total of comparisons.