Merge Sort vs Quick Sort

In this article, we have covered the differences between Merge Sort and Quick Sort (Merge Sort vs Quick Sort) and covered when to use Merge Sort over Quick Sort and vice versa. We have covered the following points:

  • Time and Space Complexity of Merge and Quick Sort
  • When to use Merge Sort over Quick Sort?
  • When to use Quick Sort over Merge Sort?
  • Differences between Merge and Quick Sort
  • Conclusion

Time and Space Complexity of Merge and Quick Sort

Following is the Time and Space Complexity of Merge Sort:

  • Average Time Complexity: O(N logN)
  • Worst Case Time Complexity: O(N logN)
  • Best Case Time Complexity: O(N)
  • Space Complexity: O(N); O(1) with Linked Lists

Following is the Time and Space Complexity of Quick Sort:

  • Average Time Complexity: O(N logN)
  • Worst Case Time Complexity: O(N^2); O(N logN) with median of medians
  • Best Case Time Complexity: O(N logN)
  • Space Complexity: O(N); O(logN) with Hoare's original version

When to use Merge Sort over Quick Sort?

Merge Sort is the preferred choice over Quick Sort when:

  • Data to be sorted is in Linked Lists

  • When the sorting algorithm needs to run in parallel

  • When a stable sorting is needed

  • Data to be sorted is in Linked Lists.
    No other sorting algorithm performs better than Merge Sort on Linked Lists. This is because access takes linear time O(N) on Linked List which makes the performance of a traditional sorting algorithm worse.
    Merge Sort performs best on Linked Lists.

  • When the sorting algorithm needs to run in parallel
    To make a sorting algorithm run in parallel in different CPU cores to accelerate performance further, Merge Sort is the best choice.
    Other sorting algorithms like Quick Sort are hard to implement for a parallel environment and will make less CPU utilization compared to Merge Sort.

  • When a stable sorting is needed

Stable Sorting means the order of elements with same value is same after the elements have been sorted. This matters as elements will have auxillary data that is additional data associated with the element.

Merge Sort is a stable sorting algorithm whereas as Quick Sort is an unstable sorting algorithm. Quick Sort can be modified to be a stable sorting algorithm but such implementations are not efficient and hence, not advised to be used.
Therefore, Merge Sort is the only choice.

When to use Quick Sort over Merge Sort?

Quick Sort is the preferred choice over Merge Sort when:

  • Array is stored in RAM

  • Better Cache Usage

  • Array is stored in RAM

If the elements are in an array and stored in RAM (Random Access Memory), then Quick Sort is the best choice.

  • Better Cache Usage

Quick Sort makes better use of cache and demonstrate better locality of reference when compared to Merge Sort. Hence, when systems have large cache, then Quick Sort should be used in practice.

Block QuickSort is a variant that makes use of cache better by reducing mis-branch predictions.

Use of Merge and Quick Sort

  • In Java's Arrays.sort(), Merge Sort and Quick Sort is used depending on the datatype and if the number of elements is less than 7, then Insertion Sort is used.
Arrays.sort(array1);
  • Python's sorting algorithm uses Timsort which is a variants of Merge Sort and Insertion Sort.
  • In C, qsort() uses an efficient Quick Sort implementation. There is no corresponding function for Merge Sort.
qsort(array);

Differences

The difference between Merge and Quick Sort are as follows:

  • Merge Sort is a stable sorting algorithm whereas Quick Sort is an unstable sorting algorithm.
  • Merge Sort performs best on Linked Lists whereas Quick Sort performs best on Arrays stored in RAM.
  • Merge Sort runs on multiple CPU cores in parallel better than Quick Sort.
  • Quick Sort makes use of cache better than Merge Sort.
  • The worst case performance of Merge Sort is O(N logN) whereas for Quick Sort, it is O(N^2).

Conclusion

Hence, both Merge Sort and Quick Sort are competitive Sorting Algorithms and is used in their own area of expertise. With the ideas in this article at OpenGenus, you must have the idea of when to use Quick Sort and when to use Merge Sort.