Given two sorted list of size m and n respectively. The number of comparisons…
2018
Given two sorted list of size m and n respectively. The number of comparisons needed the worst case by the merge sort algorithm will be
- A.
m x n
- B.
maximum of m and n
- C.
minimum of m and n
- D.
m + n - 1
Attempted by 244 students.
Show answer & explanation
Correct answer: D
To merge two sorted lists of sizes m and n, we compare elements from the front of each list. In the worst case, we continue comparing until only one element remains unmerged across both lists. This requires exactly m + n - 1 comparisons.