GATE CSE 1995 | Question: 1.16

Question

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

• A. $O(m)$

• B. $O(n)$

• C. $O(m+n)$

• D. $O(\log m + \log n)$

Comments

Why not in the  worst case it is max of m,n

Answer 1

Answer: Option C.

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

Comments

ohh.. ok sir. Thnx :)

---

If we place a sentinel($\infty$) at the end of both lists, then comparisons will also be of order $\Theta(m + n)$

---

Example for best case :

arr1 = 10 20 50 70

arr2 = 2 5 7

mini(4,3) = 3

Answer 2

$\text{A : 10  20  30  90}$

$\text{B : 40  50  60  70}$

Suppose $\text{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

Answer : $C$

Comments

Thanks for the example

---

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$

Answer 3

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++];
}
}

Answer 4

@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).

Comments

How are you knowing that you have reached the last element of one of the sorted lists? Doesn't that require another comparison?

---

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.

Answer 5

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.

Answer 6

1).For merging two sorted lists of sizes m and n into a sorted list of size m+n, we require comparisons of O(m+n) in terms of asymptotic notation. This is because during the merging process, we are comparing each element from both lists once, and the total number of elements in the merged list is m+n. Therefore, the number of comparisons is directly proportional to the number of elements in the merged list, and the asymptotic notation for the number of comparisons is O(m+n).      

2).For merging two sorted lists of sizes m and n into a sorted list of size m+n, we require comparisons of m+n-1. The reason is that in order to merge the two sorted lists, we need to compare the first element of each list and select the smaller one. Then we move on to the next element of the selected list and repeat the process. We do this until one of the lists is completely merged. At this point, we only have one list remaining which is already sorted, so we don't need to make any more comparisons. Since we make one comparison for each element in the merged list, we need m+n-1 comparisons.