When is Quicksort better than Mergesort?

Technology CommunityCategory: SortingWhen is Quicksort better than Mergesort?
VietMX Staff asked 3 years ago
Problem

They’re both O(n log n) and yet most people use Quicksort instead of Mergesort. Why is that?

  • Quicksort has O(n2) worst-case runtime and O(n log n) average case runtime. However, it’s superior to merge sort in many scenarios because many factors influence an algorithm’s runtime, and, when taking them all together, quicksort wins out.
  • Quicksort in particular requires little additional space (it’s in-place and MergeSort requires extra memory linear to number of elements to be sorted) and exhibits good cache locality (does half as many reads as the other algorithms), and this makes it faster than merge sort in many cases. In addition, it’s very easy to avoid quicksort’s worst-case run time of O(n2) almost entirely by using an appropriate choice of the pivot – such as picking it at random (this is an excellent strategy).

The average case performance for quicksort is faster than mergesort. But this is only true if you are assuming constant time to access any piece of memory on demand. In RAM this assumption is generally not too bad (it is not always true because of caches, but it is not too bad). However if your data structure is big enough to live on disk, then quicksort gets killed by the fact that your average disk does something like 200 random seeks per second.

if data has to be sorted on disk, you really, really want to use some variation of mergesort.