Question

How many comparisons are required to merge these pairs of lists using Algorithm 10?

1. 1,3,5,7,9; 2,4,6,8,10
2. 1,2,3,4,5; 6,7,8,9,10
3. 1,5,6,7,8; 2,3,4,9,10

Short answer

The recursive algorithm is given below.

Step-by-step solution

Result Used

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$L_1$ and$L_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}

From discussion on Lemma 1, the number of comparisons is m + n - r, where the lists have m and n elements, respectively, andr is the number of elements remaining in one list at the point the other list is exhausted.

Given that

Here, in all the lists m = 5 and n = 5.

So the number of comparisons is 10 - r

(a)Step 3: Comparisons required in list 1

The lists are

1, 3,5,7,9 and

2, 4, 6,8,10

Here, when the first list is emptied, the second list has only 1 element.

Thus r = 1

So, the number of comparisons required is 10 - 1 = 9

Hence, the comparisons required to merge the lists are 9

(c)Step 3: Comparisons required in list 3

The lists are:

1,5,6,7,8and

2,3,4,9,10

Here, when the first list is emptied, the second list has only 2 elements.

Thus r = 2

So, the number of comparisons required is 10 - 2 = 8

Hence, the comparisons required to merge the lists are 8.