Mergesort advantages over Quicksort are:
- Mergesort is worst-case
O(n log n)
, Quicksort is average caseO(n log n)
, but has a worst case ofO(n2)
- Mergesort is stable by design, equal elements keep their original order
- Mergesort is well suited to be implemented parallel (multithreading)
- Mergesort uses (about 30%) less comparisons than QuickSort. This is an often overlooked advantage, because a comparison can be quite expensive (e.g. when comparing several fields of database rows)
- Mergesort is a superior algorithm for sorting linked lists, since it makes fewer total comparisons
- Linked lists can be merged with only
O(1)
space overhead instead ofO(n)
space overhead
Quicksort usually is better than mergesort for two reasons:
- Quicksort has better locality of reference than mergesort, which means that the accesses performed in quicksort are usually faster than the corresponding accesses in mergesort.
- Quicksort uses worst-case
O(log n)
memory (if implemented correctly), while mergesort requiresO(n)
memory due to the overhead of merging.
Scenarios when quicksort is worse than mergesort:
- Array is already sorted
- All elements in the array are the same
- Array is sorted in reverse order