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)$

Answer 1

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 2

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.