# GATE1995-1.16

14.6k views

For merging two sorted lists of sizes $m$ and $n$ into a sorted list of size $m+n$, we require comparisons of

1. $O(m)$

2. $O(n)$

3. $O(m+n)$

4. $O(\log m + \log n)$

edited

The number of moves are however always $m+n$ so that we can term it as $\Theta(m+n)$. But the number of comparisons vary as per the input. In the best case the comparisons are $Min(m,n)$ and in worst case they are $m+n-1$.

edited
0
@Arjun Sir I think its not rght to say best case as Min(m,n). It depnds like if m>n and whichever side will contain smaller values will be finished first. It may be m or n not always minimum.. ryt sir?
2
not always- thats why it is only a best case.
1
ohh.. ok sir. Thnx :)
1
If we place a sentinel($\infty$) at the end of both lists, then comparisons will also be of order $\Theta(m + n)$
A : 10  20  30  90

B. : 40  50  60  70

Suppose A.length =m ,B.length=n

Here m+n-1 comparisons are required
So O(m+n)//this is one of  the worst case comparison
0
Thanks for the example
1
If we think there is an $\infty$ at the last of every array then there will be m+n comparison,one extra for last element as it have to compare with $\infty$

If there are 2 arrays like this

A: 10   20    60   90

B:  30   50    70  100

And store the resultent array in C[ ]

while((a[]!=NULL) && (b[]!=NULL))
{
if((a[i]<b[j])||(b[j]==NULL))
{
c[k++]=a[i++];
}
else
{
c[k++]=b[j++];
}
}
@srestha, kindly notice that in question its written two sorted list, not array.

in this case,
best case:- all elements of 2nd list is greater than that of 1st list then minimum comparison is Min(m,n) as it will take only one iteration.for comparison rest will be inserted as it is.
and worst case:- let 2 sorted list be 1,2,3,4 and 1,2,3,4 so here total comparison for merging should be =7(last element need not be compared) so total comparison= m+n-1= O(m+n).
0
How are you knowing that you have reached the last element of one of the sorted lists? Doesn't that require another comparison?
0
See srestha mam's code above, try doing a dry run through the code with the two sorted lists. The elements are compared and inserted in this order : B[0],A[0],B[1]... so like this B will be the first list to be finish and it will break out of the loop. The no. of comparisons done till here would be m+n-1. Lastly A's last element would be inserted.

Hope it helps :)

Example:

A[] = {11,22,33}

B[] = {4,12,43}

Assuming, we are sorting in ascending order.  We compare 11 and 4, smaller is 4. So, insert 4 then 11, then 11 AND 12 , insert 11. then 12 and 22 , insert 12, then 22 and 43 , insert 22, then compare 43 and 33, insert 33 and then finally remaining one 43. So, we required 5 steps for 6 elements.

To sort them we will be requiring (m+n-1) comparisons in worst case.

## Related questions

1
2.1k views
Merge sort uses: Divide and conquer strategy Backtracking approach Heuristic search Greedy approach
Consider the following sequence of numbers:$92, 37, 52, 12, 11, 25$ Use Bubble sort to arrange the sequence in ascending order. Give the sequence at the end of each of the first five passes.
Consider the following Pascal function where $A$ and $B$ are non-zero positive integers. What is the value of $GET(3, 2)$? function GET(A,B:integer): integer; begin if B=0 then GET:= 1 else if A < B then GET:= 0 else GET:= GET(A-1, B) + GET(A-1, B-1) end; The Pascal procedure given for computing the ... 1 to N - 1 do for J:=1 to N do begin TMP:= A[I, J]; A[I, J]:= A[J, I]; A[J, I]:= TMP end end;
Assume that $X$ and $Y$ are non-zero positive integers. What does the following Pascal program segment do? while X <> Y do if X > Y then X := X - Y else Y := Y - X; write(X); Computes the LCM of two numbers Divides the larger number by the smaller number Computes the GCD of two numbers None of the above