Database-Management-System

Question 557

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

Database-Management-SystemB-and-B+-TreesUGC NET CS 2013 Dec-paper-2

Question 557 Explanation:

→ To merge two lists of size m and n, we need to do m+n-1 comparisons in worst case. Since we need to merge 2 at a time, the optimal strategy would be to take smallest size lists first.
→ The reason for picking smallest two items is to carry minimum items for repetition in merging.

Correct Answer: D

Question 557 Explanation:

→ To merge two lists of size m and n, we need to do m+n-1 comparisons in worst case. Since we need to merge 2 at a time, the optimal strategy would be to take smallest size lists first.
→ The reason for picking smallest two items is to carry minimum items for repetition in merging.