64 votes

Suppose $P, Q, R, S, T$ are sorted sequences having lengths $20, 24, 30, 35, 50$ respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.

126 votes

Best answer

The optimal algorithm always chooses the smallest sequences for merging.

$20 \ 24 -44, 43$ comparisons

$30 \ 35 -65, 64$ comparisons

$44 \ 50 -94, 93$ comparisons

$65 \ 94 -159, 158$ comparisons

so, totally $43 + 64 + 93 + 158 = 358$ comparisons.

PS: In merge operation we do a comparison of two elements and put one element in the sorted output array. So, every comparison produces one output element. But for the last element we won't need a comparison and we simply insert it to the output array. So for $n$ output elements we need $(n-1)$ comparisons.

$20 \ 24 -44, 43$ comparisons

$30 \ 35 -65, 64$ comparisons

$44 \ 50 -94, 93$ comparisons

$65 \ 94 -159, 158$ comparisons

so, totally $43 + 64 + 93 + 158 = 358$ comparisons.

PS: In merge operation we do a comparison of two elements and put one element in the sorted output array. So, every comparison produces one output element. But for the last element we won't need a comparison and we simply insert it to the output array. So for $n$ output elements we need $(n-1)$ comparisons.

50

In merge operation we do a comparison of two elements and put one element in the sorted output array. So, every comparison produces one output element. But for the last element we won't need a comparison and we simply insert it to the output array. So for n output elements we need (n-1) comparisons.

3

But Sir in merge procedure in the two lists we are putting 2 infinities/large numbers at the end.

1 3 5 999 2 4 999

Here after 4 comparisons,the 1 2 3 4 comes down into the final array.lastly to copy 5 into the final array we do compare it 999 in the second list,

1 3 5 999 2 4 999

Here after 4 comparisons,the 1 2 3 4 comes down into the final array.lastly to copy 5 into the final array we do compare it 999 in the second list,

5

@Arjun sir here two possibilities are there

[A] 20 24 ->44, 43 comparisons

30 35 ->65, 64 comparisons

44 50 ->94, 93 comparisons

65 94 ->159, 158 comparisons

**totally 43 + 64 + 93 + 158 = 358 comparisons**.

[B] 20 24 ->44, 43 comparisons

30 35 ->65, 64 comparisons

44 65 -109, 108comparisons

109 50-159, 158 comparisons

**totally 43+64+108+158 =373 comaprisions**. // shouldn't we keep same order as per question P,Q,R,S,T

and question asked comaprison will be needed in **worst case by optimal algorithm,**

8

If the algorithm does like that it is no longer optimal. There is no need to keep any order unless explicitly mentioned.

5

@Arjun Sir how the program will know that it is the last element of list without seeing Infinity on list..

suppose we have two list

1st list contain 2,3

2nd list containn 4,5,6

1st comparison of (2,4) ----------->2 will come in Final Array

2nd comparison of (3,4) ----------->3 will come in Final Array

3rd comparison of (infinity, 4)----------->4 will come in Final Array

4th comparison of (infinity,5)----------->5 will come in Final Array

5th comparison of (infinity,6)----------->6 will come in Final Array

According to u 4 comparison will be needed but how when we compare infinity to 5 then how it will know that next element of 2nd list will be end element of the list

suppose we have two list

1st list contain 2,3

2nd list containn 4,5,6

1st comparison of (2,4) ----------->2 will come in Final Array

2nd comparison of (3,4) ----------->3 will come in Final Array

3rd comparison of (infinity, 4)----------->4 will come in Final Array

4th comparison of (infinity,5)----------->5 will come in Final Array

5th comparison of (infinity,6)----------->6 will come in Final Array

According to u 4 comparison will be needed but how when we compare infinity to 5 then how it will know that next element of 2nd list will be end element of the list

0

@Arjun Sir, Here we do need a min heap to select the two smallest element every time and after merging them we do need to put them backin the min heap. What about the comparisions needed to maintain the min heap? Dont we need to count them?

0

what is the best case number of comparisons performed by optimal algorithm to do the merging in above question?

0

How do we know it is the last element? For that somewhere in the program we will compare (say `loop until i<(n-1)`

) right? Won't that comparison be counted? Please solve my doubt. Thank You.

0

Hello sir, i have never read anywhere to merge two sorted lists which are smaller in size of all the given lists, this looks like more of hamilton path instead of merge procedure. Also i have a doubt when to use two-way merge sort and when to apply merge sort algorithm like explained by @Richa bhardwaj the above comments

It will be good if can have a reference to read from clearing this doubt as nothing is talked about 2-way mergin in Coreman

It will be good if can have a reference to read from clearing this doubt as nothing is talked about 2-way mergin in Coreman

5

My dear friend , why you are comparing with infinity ?

We know the lower and upper limits, once the one of the two array exhausted, we simply copy the remaining array.

1

this is not the right way of making an optimal tree.Maybe you got a correct answer in this case.For tree to be optimal we have to use greedy method.Hence after selecting (20 24) which equal to be 44 you should select (30 35) as it is another minimum pair.

0

@Prateek kumar Question doesn't say anything about the order the second thing is absolutely incorrect.

0

@Arjun Sir,

The very basic Question. You say that,"** The optimal algorithm always chooses the smallest sequences for merging"..**But,How algorithm will find,the smallest sequences,before merging for next pass?? "

0

@Headshot, how will you come to know about the array has been exhausted, for that u have to do 1 comparison, in worst case there will be one-one element present in both set, here we have to do 1 comparison, who is smaller, after putting the smaller one, we have to do one more comparison to know that one array has been exhausted, then only we can copy the element.

0

No, in the worst case both array would be same, according to the implementation the while loop will break whenever even one of the array is exhausted. **The comparison doesnt mean to check array is exhausted its to check which element has to be inserted among the two arrays**. If there is one- one element you will do 1 + 1 - 1 comparison because after inserting one element from either of the two arrays, one will be exhausted so while loop will break. So there is only one comparison.

0

// Merge arr1[0..n1-1] and arr2[0..n2-1] into arr3[0..n1+n2-1] void mergeArrays(int arr1[], int arr2[], int n1, int n2, int arr3[]) { int i = 0, j = 0, k = 0; while (i < n1 && j < n2) { // Check if current element of first array is smaller than current element // of second array. If yes, store first array element and increment first // array index. Otherwise do same with second array if (arr1[i] < arr2[j]) arr3[k++] = arr1[i++]; else arr3[k++] = arr2[j++]; } // Store remaining elements of first array while (i < n1) arr3[k++] = arr1[i++]; // Store remaining elements of second array while (j < n2) arr3[k++] = arr2[j++]; }

If the input is worst case, after comparing $n1+n2-1$ elements while loop breaks.

Source: https://www.geeksforgeeks.org/merge-two-sorted-arrays/

0

@Arjun sir if we consider the merge process of the **Merge Sort**, Then the minimum number of comparisons it takes is **min(length of sorted array1, min length of sorted array 2)**.

So if we go by that approach the answer comes out to be different.

I can’t get why are we requiring the comparisons to be **n1+n2-1.**

0

consider Merging these two arrays …

A[] =1,2,7,11,**88**,**100**

B[] =8,9,90,91,__ 98__,

here when you are merging A and B in C. array.

c=1,2,7,8,9,11,88,90,91,98 ,100,107….You have to go till end of both array and compare 100,107 ...and put 100 in C first….

Why this happend?

because last element of Array A i.e. 100 is bigger than second last element of array B(i.e. 98) (worst case)

Nowe consider A=1,2,3 B=4,5,6,7,8,9,10

c=1,2,3,4,5,6,7,8,9,10

here how many comparison required? 3 because array A has 3 elements all less than B(best case)

so to merge array of size m and size n

**min(m,n)<= no of comparison<=m+n-1**

21 votes

7 votes

5 votes

1 vote

In the above implementation, total number of comparisons is

(44-1) + (94-1) + (65-1) + (159-1) = 358

**Hint: The number of comparisons for merging two sorted sequences of length m and n is m+n-1.**

1 vote

Let Question says for Best case. ( Expected in Gate)

than answer is → 159.

because when we apply Merge sort between (20, 24), in Best case 20 comparison required and in worst case it is (20 + 24 -1 ).

Now just take best case only –

1st) merging (20 , 24) → 20 comparison and new list has 44 elements.

2nd) merging (30, 35) → 30 comparison and new list has 65 elements.

3rd) merging (44 , 50) → 44 comparison and new list has 94 elements.

4th) merging (65, 94) → 65 comparison and new list has 159 elements.

------

Total → (20 + 30 + 44 + 65 ) = 159.

If You find any mistake than plz comment below else UPVOTED :)

than answer is → 159.

because when we apply Merge sort between (20, 24), in Best case 20 comparison required and in worst case it is (20 + 24 -1 ).

Now just take best case only –

1st) merging (20 , 24) → 20 comparison and new list has 44 elements.

2nd) merging (30, 35) → 30 comparison and new list has 65 elements.

3rd) merging (44 , 50) → 44 comparison and new list has 94 elements.

4th) merging (65, 94) → 65 comparison and new list has 159 elements.

------

Total → (20 + 30 + 44 + 65 ) = 159.

If You find any mistake than plz comment below else UPVOTED :)