8-6

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 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. ${{2n}\choose {n}}$
b. $${{2n}\choose {n}}$$ $$2n!/{n!}^2}$$ using stirling approximation $$\sqrt{4\pi n}. (2n/e)^2/(\sqrt{2\pi n} e^{1/12n})^2$$ for binary tree there will be $2^h$ leaves $$2^h = 2n - log 2\pi n$$ $$2^h = 2n - O(n)$$ c. If two list are sorted by merge procedure and the list needed to be merged. Since the elements are in two different lists we dont know if they are equal or greater or less than to know the relationship we need to compare them and arrange in the final array according to the order.

d. Lets assume the elements in first sorted list $L = {l_1,l_2...1_n}$ and second sorted list as $R= {r_1,r_2,r_3,r_4..r_n}$ if the elements in L list are all equal and greater than every element in R list. Then the merge procedure will compare the first element($l_1$) in the L list to every element in L the number of comparisons are n-1 and also according to c we need to compare two elements if they are consecutive in sorted order and from different list. Now since $l_1$ is greater than every element in R list we compare n times. Hence the running time is 2n -1.