Question

Show that for all positive integers m and n there are sorted lists with m and n elements, respectively, such that Algorithm 10 uses m + n - 1 comparisons to merge them into one sorted list.

Short answer

It has been proved that for all positive integers’ m and n there are sorted lists with m and n elements, respectively, such that Algorithm 10 uses m + n - 1 comparisons to merge them into one sorted list.

Step-by-step solution

Algorithm 10

Algorithm 10 is about the merging of two lists.

proceduremerge ( $L_1{L}_2$: sorted lists)

L := empty list

while $L_1$and $L_2$are both nonempty

remove smaller of the first element of data-custom-editor="chemistry" $L_1\mathit{}and\mathit{}{L}_{\mathit{2}}$ from its list; put it at the right end of L

if this removal makes one list empty then remove all the elements from the other list and

apprehend them to L

return L {L is the merged list with elements in increasing order}

Proof.

Make sure that one of the lists is exhausted only when the other list has only one element left in it.

In this case, a comparison is needed to place every element of the merged list into place,

except for the last element.

This condition is met if and only if the largest element in the combined list is in one of the initial lists and the second largest element is in the other.

One such pair of lists is$\left\{1,2,...,m-1,m+n\right\}and\left\{m,m+1,...,m+n-1\right\}$.