recategorized by
8,247 views

2 Answers

Best answer
4 votes
4 votes

The number of comparisons needed in the worst case by the merge sort algorithm will be m+n-1 i.e. only last element will not be compare only.

selected by
1 votes
1 votes

(D) m+n-1 ..

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...

Answer:

Related questions

2 votes
2 votes
2 answers
1
go_editor asked Jul 26, 2016
3,163 views
Big-O estimate for $f(x)=(x+1) \log(x^2 +1) + 3x^2 $ is given as$O(x \log x)$$O(x^2)$$O(x^3)$$O(x^2 \log x)$
1 votes
1 votes
1 answer
2
go_editor asked Jul 25, 2016
3,686 views
For any B-tree of minimum degree t $\geq$ 2, every node other than the root must have at least ____ keys and every node can have at most ____ keys.t-1, 2t+1t+1, 2t+1t-1, ...
1 votes
1 votes
1 answer
3
go_editor asked Jul 26, 2016
2,871 views
Linux operating system usesAffinity schedulingFair Preemptive SchedulingHand ShakingHighest Penalty Ratio Next