When Merge Sort is preferred over Quick Sort?

Mergesort advantages over Quicksort are:

• Mergesort is worst-case O(n log n), Quicksort is average case O(n log n), but has a worst case of O(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 of O(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 requires O(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