Originally Posted by Wikipedia
Mergesort has an average and worst-case performance of O(n log n). In the worst case, merge sort does about 30% fewer comparisons than quicksort does in the average case; thus merge sort very often needs to make fewer comparisons than quicksort. In terms of moves, 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 much time as the worst case.
However, merge sort performs 2n - 1 method calls in the worst case, compared to quicksort's n, thus has roughly twice as much recursive overhead as quicksort. Mergesort's most common implementation does not sort in place, meaning memory the size of the input must be allocated for the sorted output to be stored in. Sorting in-place is possible but requires an extremely complicated implementation.
