Given two sorted list of size ‘m’ and ‘n’ respectively. The number of…
2013
Given two sorted list of size ‘m’ and ‘n’ respectively. The number of comparison needed in the worst case by the merge sort algorithm will be
- A.
m × n
- B.
max (m, n)
- C.
min (m, n)
- D.
m + n – 1
Attempted by 753 students.
Show answer & explanation
Correct answer: D
Key idea: merge by repeatedly comparing the first elements of the two lists and moving the smaller one into the output.
Each comparison produces one element for the merged output (the smaller of the two current elements).
This continues until one list becomes empty; at that point the remaining elements from the other list are copied without further comparisons.
Worst case occurs when elements are interleaved so comparisons continue until only one element remains unplaced, giving a total of (m + n) - 1 comparisons.
Therefore the number of comparisons needed in the worst case is m + n - 1.