Give a 2n1 lower bound on the number of comparisons needed t

Give a (2n1) lower bound on the number of comparisons needed to merge two sorted lists (a1, a2, . . . , an) and (b1, b2, . . . , bn) with a1 < a2 < · · · < an and b1 < b2 < · · · < bn. [Hint: Use an adversarial method. Why can’t you have in general 2n 2 or fewer comparisons?]

Solution

There are two lists a1, a2... an and b1, b2.... bn

ai<aj and bi<bj for i <j

First check whether a1<b1 or not

If true, a1 will be the first entry otherwise b1 will be the first entry

Similarly if an>bn then an is the last otherwise bn will be the last.

To merge the two in ascending order

first write the first and the last.
Then one by one consider entry from second set and find where it is to be placed.

Like that we do for each.

Hence minimum comparisons to be done is for 2n elements in total and hence done for 2n-1 times.

2n-2 comparisons or fewer will not give full ascending order as some entries would be left over.