edited by
24,624 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

Best answer
152 votes
152 votes
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
24 votes
24 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. 

13 votes
13 votes

Solution: 158+64+93+43=358

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?

Answer:

Related questions

47 votes
47 votes
3 answers
1
go_editor asked Sep 28, 2014
13,511 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 ______...