GATE CSE 2014 Set 2 | Question: 38

Question

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 ____.

Comments

>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

---

https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_optimal_merge_pattern.htm

 

This question is based on the algorithm - Optimal merge pattern. For more understanding of this algorithm visit the above link.

Answer 1

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.

Comments

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 ??

Any rspected sir/madam please clear my doubt.

Thanx in advance

---

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

Answer 2

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. 

Comments

Yes we can solve it using Huffman coding easily.

Answer 3

Solution: 158+64+93+43=358

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?

---

yes it will

Answer 4

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?

Comments

nice solution