Help formulating a proof showing two lists can be merged with 2n-1 comparisons

Question

I need some help formulating a proof that shows that two lists of size n can be merged in 2n - 1 comparisons. I understand the essence behind it, but have difficulty proving it mathematically.

I understand that the worst case occurs when merging two lists of size n, the two lists only contain elements that are interleaved. For example:

List 1: [1, 3, 5]

List 2: [2, 4, 6]

Starting off with the first element in List 1:

1 < 2 ? yes. Output = [1]

3 < 2 ? no. Output = [1, 2]

3 < 4 ? yes. Output = [1, 2, 3]

5 < 4 ? no. Output = [1, 2, 3, 4]

6 < 5 ? no. Output = [1, 2, 3, 4, 5]

Append last element: Output = [1, 2, 3, 4, 5, 6]

Any tips on how I can start developing a mathematical proof for this?

Answer 1

The best thing is to explicitly write down a corresponding algorithm, such as

Given sorted input lists $L_1$, $L_2$ of lengths $n,m$, produce a merged (sorted) list $O$.

1. [Init] Set $O$ to the empty list.
2. [Done?] If $L_1$ or $L_2$ is empty, append $L_1$ to $O$ and append $L_2$ to $O$ and terminate.
3. [Compare; note that both lists are nonempty] If the head of $L_1$ is $<$ the head of $L_2$ goto step 5
4. [output next] append the head of $L_2$ to $O$ and remove it from $L_2$. Then go to step 2
5. [alternative output next] append the ehad of $L_1$ to $O$ and remove it from $L_1$. Then go to step $2$.

Then use the usual tools to analize an algorithm that step 3 is executed exactly $m+n-1$ times if $m,n>0$ (and $0$ times if one of $m,n$ is zero).

Answer 2

Look at the algorithm. Every time you made a comparison, you immediately added an element to the output list. And then you added one more element to the output list without making a comparison.

If both input lists have $n$ elements each, the output list has $2n$ elements. Size of output $\geq$ number of comparisons, so it is easy to show $2n$ is an upper bound. To decrease the bound to $2n-1$, you need to show that the last element of output is always written without a comparison.

The worst case is actually whenever the last element of one list is between the last two elements of the other list, so that there is always something in each input list until the time when you can write the very last element. The number of comparisons is not affected by how the rest of elements in the lists are interleaved.

Answer 3

We all agree that the procedure consists in comparing the smallest element in $A$ with the smallest element in $B$ and removing the smallest of the two. We do this until one of the lists empties.

As there are $2n$ elements in total, we can't do more than $2n-1$ deletions (when a single element is left, one of the lists is empty).

This bound can be achieved in the worst case, for instance if we always remove an element from the largest set.