no of comparisons

Question

What are the number of comparisons in merge sort?

m+n or m+n-1...

Comments

This “min(m,n) comparisons in best case” is for the merge step of Merge sort, Not for entire merge sort. Merge sort takes, in every case, $O(nlogn)$ comparisons for $n$ elements.

Merge sort’s best case is when the largest element of one sorted sub-list is smaller than the first element of its opposing sub-list, for every merge step that occurs. Only one element from the opposing list is compared, which reduces the number of comparisons in each merge step to N/2.

This “(n/2) comparisons in best case” is for final merge step of Merge sort, Not for entire merge sort. Merge sort takes, in every case, $O(nlogn)$ comparisons

Answer 1

In best case it  is  min(m, n)  if we consider number of elements in one array is m and in other it is n..

However in worst case it will take m+n-1 comparisons..when alternate element goes into 3rd array which is merged and sorted array..

However number of merges will be same in all cases which is m+n.. 

​​​​​​

Comments

@HabibKhan Sir can u please elaborate how exactly this can be done in more specific way.. I know how the asymptotic notation can be derived for this but I am unable to understand  how to generalize the exact number of comparision here for both Best and Worst case..

---

Let me explain. If you have 2 array 1 2 3 9 infi and 4 5 6 7 infi. If you do the comparison then 1 2 3 will be placed and then due to 9 ,  4 5 6 7 will be placed and as the computer will see the pointer at the end of second list it will place 9. As taught infinity is just to see the end . 4 + 4 -1 = 7 comparsions

---

This “min(m,n) comparisons in best case” is for the merge step of Merge sort, Not for entire merge sort. Merge sort takes, in every case, $O(nlogn)$ comparisons for $n$ elements.

Merge sort’s best case is when the largest element of one sorted sub-list is smaller than the first element of its opposing sub-list, for every merge step that occurs. Only one element from the opposing list is compared, which reduces the number of comparisons in each merge step to N/2.

This “(n/2) comparisons in best case” is for final merge step of Merge sort, Not for entire merge sort. Merge sort takes, in every case, $O(nlogn)$ comparisons