Merge sort has the following performance characteristics:
- Best case:
O(n log n) - Average case:
O(n log n) - Worst case:
O(n log n)
Quicksort has the following performance characteristics:
- Best case:
O(n) - Average case:
O(n log n) - Worst case:
O(n^2)
Quicksort has a best-case linear performance when the input is sorted, or nearly sorted. It has a worst-case quadratic performance when the input is sorted in reverse, or nearly sorted in reverse.
Merge sort performance is much more constrained and predictable than the performance of quicksort. The price for that reliability is that the average case of merge sort is slower than the average case of quicksort because the constant factor of merge sort is larger. However, this constant factor greatly depends on the particular details of the implementation. A good merge sort implementation will have better average performance than a poor quicksort implementation.