Given two sorted lists of size m and n respectively. The number of comparisons…
2017
Given two sorted lists of size m and n respectively. The number of comparisons needed in the worst case by the merge algorithm will be:
- A.
m + n − 1
- B.
mn
- C.
max (m, n)
- D.
min (m, n)
Attempted by 812 students.
Show answer & explanation
Correct answer: A
Correct Answer: m + n − 1
Merge process: Repeatedly compare the smallest remaining elements of the two sorted lists and move the smaller one into the output. Each such comparison places exactly one element into the merged list.
Worst case: To place all m + n elements you need at most m + n − 1 comparisons. After m + n − 1 placements only one element remains, and it can be appended directly without any further comparison. This worst case arises when the two lists interleave so that one list is not exhausted early.
Example: For m = 3 and n = 2, merging [1, 3, 5] and [2, 4] requires 4 comparisons = 3 + 2 − 1.