in Algorithms edited by
18,315 views
73 votes
73 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 ____.
in Algorithms edited by
by
2699 3558 3939
18.3k views

4 Comments

what does optimal algorithm mean here?
0
0
what does worst case mean and how can we find it?
0
0
>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)
2
2

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

2
2

Subscribe to GO Classes for GATE CSE 2022

7 Answers

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

5 Comments

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

 

2
2
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.
1
1
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 ??

Any rspected sir/madam please clear my doubt.

Thanx in advance
0
0

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

0
0
22 votes
22 votes

To merge two lists of size m and n, we need to do m+n-1 comparisons in worst case. Since we need to merge 2 at a time, the optimal strategy would be to take smallest size lists first. The reason for picking smallest two items is to carry minimum items for repetition in merging. We first merge 20 and 24 and get a list of 44 using 43 worst case comparisons. Then we merge 30 and 35 into a list of 65 using 64 worst case comparisons. Then we merge 50 and 44 into a list of 94 using 93 comparisons. Finally we merge 94 and 65 using 158 comparisons. So total number of comparisons is 43 + 64 + 93 + 158 which is 358. 

by
21 69 161

1 comment

Yes we can solve it using Huffman coding easily.
1
1
9 votes
9 votes

Solution: 158+64+93+43=358

by
29 88 173

2 Comments

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

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

1 comment

edited by

nice solution

0
0
3 votes
3 votes
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 :)

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 . 

0
0
1 vote
1 vote

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

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.

Answer:

Related questions