When merge sort is preferred over Quick sort?

Question

Quick sort is much better than merge sort in many cases. Though, when are the cases when merge sort might be a better solution than quick sort?

For example, merge sort works better than quick sort when data cannot be loaded to memory at once. Are there any other cases?

EDIT: Answers of the suggested duplicate question list all advantages of quick sort over merge sort. I'm asking here about the possible cases and applications that using merge sort in would be advantageous than using quick sort.

Solution 1

I should probably start off by mentioning that both quicksort and mergesort can work just fine if you can't fit everything into memory at once. You can implement quicksort by choosing a pivot, then streaming elements in from disk into memory and writing elements into one of two different files based on how that element compares to the pivot. If you use a double-ended priority queue, you can actually do this even more efficiently by fitting the maximum number of possible elements into memory at once.

Others have mentioned the benefit that mergesort is worst-case O(n log n), which is definitely true. That said, you can easily modify quicksort to produce the introsort algorithm, a hybrid between quicksort, insertion sort, and heapsort, that's worst-case O(n log n) but retains the speed of quicksort in most cases.

It might be helpful to see why quicksort is usually faster than mergesort, since if you understand the reasons you can pretty quickly find some cases where mergesort is a clear winner. Quicksort usually is better than mergesort for two reasons:

1. 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.

2. Quicksort uses worst-case O(log n) memory (if implemented correctly), while mergesort requires O(n) memory due to the overhead of merging.

There's one scenario, though, where these advantages disappear. Suppose you want to sort a linked list of elements. The linked list elements are scattered throughout memory, so advantage (1) disappears (there's no locality of reference). Second, linked lists can be merged with only O(1) space overhead instead of O(n) space overhead, so advantage (2) disappears. Consequently, you usually will find that mergesort is a superior algorithm for sorting linked lists, since it makes fewer total comparisons and isn't susceptible to a poor pivot choice.

Hope this helps!

Solution 2

A single most important advantage of merge sort over quick sort is its stability: the elements compared equal retain their original order.

Solution 3

1. MergeSort is stable by design, equal elements keep their original order.
2. MergeSort is well suited to be implemented parallel (multithreading).
3. 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).

Solution 4

Quicksort is average case O(n log n), but has a worst case of O(n^2). Mergesort is always O(n log n). Besides the asymptotic worst case and the memory-loading of mergesort, I can't think of another reason.

Scenarios when quicksort is worse than mergesort:

1. Array is already sorted.
2. All elements in the array are the same.
3. Array is sorted in reverse order.

Take mergesort over quicksort if you don't know anything about the data.

Solution 5

Merge sort has a guaranteed upper limit of O(N log₂N). Quick sort has such limit, too, but it is much higher - it is O(N²). When you need a guaranteed upper bound on the timing of your code, use merge sort over quick sort.

For example, if you write code for a real-time system that relies on sorting, merge sort would be a better choice.

View more solutions