edited by
24,626 views
86 votes
86 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 ____.
edited by

8 Answers

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 votes
1 votes

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.

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

47 votes
47 votes
3 answers
1
go_editor asked Sep 28, 2014
13,512 views
The number of distinct minimum spanning trees for the weighted graph below is _____
44 votes
44 votes
7 answers
2
27 votes
27 votes
5 answers
3
go_editor asked Sep 28, 2014
11,369 views
Consider the function func shown below: int func(int num) { int count = 0; while (num) { count++; num>>= 1; } return (count); }The value returned by func($435$) is ______...