Question

What is the best and average case of merge sort?

Answer 1

In the worst case, merge sort does about 39% fewer comparisons than quicksortdoes in the average case. In terms ofmoves, merge sort's worst case complexity is O(n log n)—the same complexity as quicksort's best case, and merge sort's best case takes about half as many iterations as the worst case.