18,315 views
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 ____.

what does optimal algorithm mean here?
what does worst case mean and how can we find it?
>optimal algorithm

means one of the best algorithm.

worst case

> kind of upper bound (means given any input algo. will not take more time then worst case)

Notice difference in framing of question: https://gateoverflow.in/466/gate1999-2-20

### Subscribe to GO Classes for GATE CSE 2022

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.
by
2437 3623 5535

consider Merging these two arrays …

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

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

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

I do not know whether there is any standard merging algorithm or not… All the texts usually talk about asymptotic times so as such they do not deal with “COMPARISONS” in a raw manner to a great extent. This concept of two way merging can be found in DATA STRUCTURES USING C AND C++ by TANENBAUM.

But the thing is that an alternative of this algo exists in CLRS where the authors have made use of sentinel at the end of the array to reduce the line of the code and increase readability.

But as far as optimality of the no. of  comparisons is concerned the one in CLRS is not optimal…

Anyways the question seems a bit weird to me, with so many literatures, implementing merging, they could have given the algo as well. Anyways it is okk.
Heyii.. I have one doubt. If one affray has exhausted then we simply copy then it means no  comparison then how we will get n-1 comparison .

For example: 1st sorted array contain 1,2,3 and 2nd sorted array contain 4,5,6 then only 1,2,3 will compare to 4 and store in final sorted array and remaing elements of 2nd array 4,5,6 these will just copy in to final array with no comparisons then how n-1 comparisons ??

for those who didnt get why comparison -1

1 2 3 large number    5 6 large num  = 5 number after mergest 5-1 comparsion required

1 compared with 5 ---------→ 1 comparison

2 compared with 6 ------------------>2 comparison

3 compared with 5 ---------------------→ 3 comparison

5 compared with large num ---------→ 4 comparison

note since we now knew that it is the end of the first sequence we are given in question P,Q,R, S,T are sorted sequences so we can place rest of elements of sequence two with out comparing because sequences already sorted

by
21 69 161

### 1 comment

Yes we can solve it using Huffman coding easily.

Solution: 158+64+93+43=358

by
29 88 173

Is it perfect method? Calculating movement and subtracting it by 1 on each parental node will give number of comparison. Will it work everywhere?
yes it will

Merging two sorted array of m & n elents take m+n-1 in worst case .. I used this approach but I want to verify it will work for all or not work always or not?

by
4 23 51

edited by

## nice solution

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

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 :)

### 1 comment

we apply Merge sort between (20, 24)

It is not merge sort it is merging of two sorted list containg 20 and 24 element .

The implementation of an optimal algorithm for merging sequences is as follows.

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.

by
1 1 2

### 1 comment

thanks :)

The implementation of optimal algorithm for merging sequences is as follows.

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.