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:
1. m × n
2. minimum of m, n
3. maximum of m, n
4. m + n - 1

Answer 1

Correct Answer - Option 4 : m + n - 1

Concept:

Merge sort algorithm uses Divide and Conquer. Hence, we divide both our lists into m and n single-element lists respectively.

Now, we know that first m lists are sorted and after these m lists, the n lists are also sorted.

Let’s call these single element lists as m1, m2 and so on, and n1, n2 and so on.

To merge these lists into one single-sorted list, we compare

• m1 with n1.
• Either m2 with n1 or m1 with n2. Here, for sorting 3 elements, 2 comparisons are needed.
• Observe that, each element in subset of m needs to be compared with each element in subset of n. We don’t need to compare m1 with other m lists because they are sorted and same goes for n lists.
• We repeat the process until we have got a sorted list with m + n elements. This happens when we have made m + n – 1 comparisons.