ISRO2018-35

Question

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 \times n$
• B. maximum of $m$ and $n$
• C. minimum of $m$ and $n$
• D. $m+n-1$

Answer 1

option d

worst case comparisons in merge sort is o(m+n-1)

Comments

Why not C .....Both  list are  already Sorted after minimum of (m,n) no. of comparison all remaining element  get copied without comparison.

---

consider the below two lists which are sorted but requries 'm+n-1'  comparissions

 

{11,13,15,17},{12,14,16,18}

---

How many for best case ??

---

min(m,n)

---

It depends , either max(m,n) or min(m,n) . Out of these two cases , one of the answer is possible and which one is to choose out of these two is completely depends on particular arrays .