The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+36 votes
4.3k 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 ____.
asked in Algorithms by Veteran (103k points)
edited by | 4.3k views
0
what does optimal algorithm mean here?
0
what does worst case mean and how can we find it?
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)

5 Answers

+83 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.
answered by Veteran (359k points)
edited by
+6
why we are subtracting 1 from all comparisons
+36
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.
+2
But Sir in  merge procedure in the two lists we are putting 2 infinities/large numbers at the end.

1 3 5 999 2 4 999

Here after 4 comparisons,the  1 2 3 4 comes down into the final array.lastly to copy 5 into the final array we do compare it 999 in the second list,
+2

@Arjun sir here two possibilities are there
[A]   20 24 ->44, 43 comparisons 
       30 35 ->65, 64 comparisons 
       44 50 ->94, 93 comparisons 
       65 94 ->159, 158 comparisons 

totally 43 + 64 + 93 + 158 = 358 comparisons.


[B]  20 24 ->44, 43 comparisons 
      30 35 ->65, 64 comparisons 
      44 65 -109, 108comparisons 
     109 50-159, 158 comparisons

totally 43+64+108+158 =373 comaprisions.       // shouldn't we keep same order as per question P,Q,R,S,T 

and question asked comaprison will be needed in worst case by optimal algorithm,

+3
If the algorithm does like that it is no longer optimal. There is no need to keep any order unless explicitly mentioned.
0
okay, got it thanks :)
+3
@Arjun Sir how the program will know that it is the last element of list without seeing Infinity on list..

suppose we have two list

1st list  contain 2,3

2nd list containn 4,5,6

1st  comparison of (2,4)  ----------->2 will come in Final Array

2nd comparison of (3,4) ----------->3 will come in Final Array

3rd comparison of (infinity, 4)----------->4 will come in Final Array

4th comparison of (infinity,5)----------->5 will come in Final Array

5th comparison of (infinity,6)----------->6 will come in Final Array

According to u 4 comparison will be needed but how when we compare infinity to 5 then how it will know that next element of 2nd list will be end element of the list
0
Excellent question
Excellent ans
0
@Arjun Sir,  Here we do need a min heap to select the two smallest element every time and after merging them we do need to put them backin the min heap. What about the comparisions needed to maintain the min heap? Dont we need to count them?
0
what is the best case number of comparisons performed by optimal algorithm to do the merging in above question?
0

The answer isAccording to the algorithm of merge sort

0

How do we know it is the last element? For that somewhere in the program we will compare (say loop until i<(n-1)) right? Won't that comparison be counted? Please solve my doubt. Thank You.

0
why total comparison -1, can you show example please..
0
Hello sir, i have never read anywhere to merge two sorted lists which are smaller in size of all the given lists, this looks like more of hamilton path instead of merge procedure. Also i have a doubt when to use two-way merge sort and when to apply merge sort algorithm like explained by @Richa bhardwaj the above comments

It will be good if can have a reference to read from clearing this doubt as nothing is talked about 2-way mergin in Coreman
0
I have the same doubt. Someone please clarify
0

you can see here he explained so well

+11 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. 

answered by Loyal (8.5k points)
+4 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?

answered by Active (3.7k points)
0

nice solution

+3 votes

Solution: 158+64+93+43=358

answered by Active (4.4k points)
0
Is it perfect method? Calculating movement and subtracting it by 1 on each parental node will give number of comparison. Will it work everywhere?
–7 votes
ans is 267
answered by (-3 points)
0
How? Please provide explanation also.
0

Taniya Mathur can u plz explain.......



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,065 questions
47,661 answers
147,308 comments
62,381 users