When is mergesort preferred over quicksort?

Question

Quicksort is better than mergesort in many cases. But when might mergesort be better than quicksort?

For example, mergesort works better when all data cannot be loaded to memory at once. Are there any other cases?

Answers to the suggested duplicate question list advantages of using quicksort over mergesort. I'm asking about the possible cases and applications where mergesort would be better than quicksort.

Mattress

Answer 1

Both quicksort and mergesort can work just fine if you can't fit all data 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.

Mergesort is worst-case O(n log n). 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.

Disparagement

In addition, mergesort is ordinarily an in-place sort, useful when sorting by column headers. – Tegument

@Tegument That is wrong! The most common implementation of mergesort has space complexity O(n) and thus it is not in-place. There are implementations which are in-place, but either they are not stable as the orignal one or they increase performance complexity. Reference: en.wikipedia.org/wiki/Merge_sort – Kolva

@AlanEvangelista The case I was discussing in the second half, where the elements are linked list, does not actually require linear auxiliary memory. We can simply shuffle around the links between the elements in the list to form the necessary sublists, rather than, say, copying those elements to temporary arrays. Check the info box on the Wikipedia page for confirmation. – Disparagement

@Disparagement Yes, I am aware that mergesort's space complexity is O(1) when ordering linked lists, my previous comment referred exclusively to xpda's incorrect statement that that is also valid for the ordinary mergesort. – Kolva

@Disparagement mergesort is also preferred over quicksort when a stable sort is required (quicksort is an unstable sort) or when comparisons are very expensive ( mergesort does more moves, but less comparisons than quicksort). It'd be nice to add those cases to your answer. – Kolva

@AlanEvangelista It's a difference in terminology. By in-place, I meant that if there are records with identical keys being sorted, they will remain in their original order after being grouped by sort key. For example, if my email has been sorted by date, and then I sort it by sender using a merge sort, the email will end up sorted by sender, date. I was not referring to space complexity. – Tegument

@Tegument I see. That's usually called a "stable sort", which is indeed one of the advantages of mergesort over quicksort (as I mentioned in my last comment) – Kolva

Quick sort worst case space complexity is O(n) not O(log n). Consider a sorted array using quick sort without randomization of choice of pivot. – Diwan

@Diwan There’s a standard optimization you can perform on quicksort that’s essentially a tail-call elimination. Rather than making two recursive calls, fire off a recursive call on the smaller of the two subarrays, then reuse the space from the current stack frame for the larger subarray. Since the size of the subarray processed in each new recursive call is at most half the size of the previous one, the total space used is O(log n). – Disparagement

@Disparagement Ooo I didn't know that. – Diwan

Answer 2

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

Dewayne

Answer 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).

Edita

Can you provide sources for 2 & 3? Also, isn't quicksort also suitable for multithreading? – Vivianna

@blumonkey - I wrote source code on my own, it is a parallel mergesort implementation in C#. There is rarely a problem, which can be divided better into independend sub tasks as this algorithm. About the comparisons, Wikipedia has the same information and it corresponds to my own tests. – Edita

Another source for 2 is the book Introduction to Algorithms by Thomas H. Cormen et al, Third edition. There is a full section explaining how to implement a multithreaded version of merge sort. The Section is 27.3 Multithreaded merge sort, page 797. – Emunctory

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

Karie

For scenarios #1 and #3, it depends on how you pick the pivot. Pretty much every common implementation uses best-of-three to avoid those two specifically. Worst case is still O(n^2), but there's no simple pattern to reach that case. Same number of patterns, they're just not simple. – Ajar

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

Milldam

Answer 6

1. Merge Sort Worst case complexity is O(nlogn) whereas Quick Sort worst case is O(n^2).
2. Merge Sort is a stable sort which means that the same element in an array maintain their original positions with respect to each other.

Stithy

This has already been answered several times in the other answers. – Kasiekask