GATE CS 1995 Q1.16 — Searching, Sorting, Hashing

To merge two sorted lists of sizes $m$ and $n$ into a single sorted list of size $m+n$, we use the standard two-pointer merging technique:

1. Compare the elements at the current pointers of both lists.
2. Append the smaller element to the merged list and advance its corresponding pointer.
3. Repeat this process until one of the lists is completely traversed, then copy the remaining elements of the other list directly.

Complexity Analysis:

• Best-case comparisons: $\min(m, n)$ (when all elements of one list are smaller than the smallest element of the other list).
• Worst-case comparisons: $m + n - 1$ (when the elements of the two lists are interleaved, requiring comparisons until only one element remains).

In the asymptotic sense, the number of comparisons required is $O(m+n)$.

Therefore, the correct option is C.