NIELIT 2017 DEC Scientific Assistant A - Section B: 53

Question

Given two sorted list of size '$m$' and '$n$' respectively. The number of comparisons needed in the worst case by the merge sort algorithm will be :

• A. $m^{*}n$
• B. minimum of $m, n$
• C. maximum of $m, n$
• D. $m+n-1$

Answer 1

The worst case will be 0(m+n-1) where “m” and “n” are the sizes of the respective lists. 

Why “-1” at the end?

because when the two lists are being compared and sorted, at the end 1 element might be left which requires no comparison, hence -1.