Comparisons in merge sort

Question

Can pls someome. Tell.number of comparisons in. Merge sort in best case as well as worst case.

Acc to. Me, at. Each level we need O(n) comaprisons and number of levels are log n in merge sort(whether it. Is a best case or worst case).hence mumber o comparisons should be nlogn in worst case as well as best case.

 

Pls guide me.

Comments

standard merge sort can't stop in between so best ,avg, worst will have O(nlogn)

Answer 1

In merge sort whatever may be sequence of inputs average best worst all cases has same nlogn complexity

Each level we need O(n) comaprisons and number of levels are log n in merge sort  is true

Comments

If we write in asymptotic notation then no of comparison in both the case = O(nlog n).

But if we have to find exact no of comp. in the best case and in the worst case then following two example can help - 

Best case   - 1, 2, 3, 4, 5, 6, 7, 8

Total no of comparisons = 12.

Worst case - 2, 5, 8, 4, 1, 7, 6, 3

Total no of comp.           = 17.   

---

what is the number of comparision if it will be two way merge sort?

---

How are you counting the total number of comparisions.. Please help..

Answer 2

in worst case number of comparisions required  nlogn 

in best case it is half = nlogn/2