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,

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 ©, 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.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用