Difference between Quick sort, Merge sort and Heap sort

Question

We know all the above-mentioned sorting algorithms take $\mathcal{O}(\mbox{N log N})$. Merge sort and Heap sort algorithms take $\mathcal{O}(\mbox{N log N})$ time in worst-case where Quicksort takes $\mathcal{O}(\mbox{N}^2)$. So what is the main difference between these algorithms? Which algorithm is preferable for sorting at any time?

Actually, I have been asked this in an interview. I replied Merge sort is not good with space. So we can consider Quicksort. But I couldn't figure out the difference between quick sort and heap sort. I need your help to figure it out.

Answer 1

Sorting is well researched area in the history of computer science and mathematics, so there are a lot of algorithms for sorting. When comparing sort algorithms, I suggest categorizing them from the following view points.

1. time complexity As already discussed in the other answers, the three algorithms are in average case $O (n \log n)$ while quick sort worst case is $O (n^2)$.
2. space complexity, especially if it's in-place sort Heap sort and quick sort can be done in-place. So they can directly work on the pre-allocated space where initial unsorted data is stored. While heap sort removes recursive calls by tail optimization and its space requirement is $O(1)$, quick sort requires variables put on the stacks at each recursive step, so it requires in total $O (\log n)$ space. Merge sort is not in-place and requires additional $O(n)$ space.
3. external sort or not This means whether the algorithm works efficiently with external memory (e.g. HDD/SSD) which is slower than the main memory. Merge sort and quick sort are typical external sort since they can divide target data set and work on the small pieces loaded on memory, but heap sort is difficult to do that.
4. stable or unstable As Karan Suraj mentioned Merge sort is only the stable sorting among the three.
5. comparison based or not Some algorithms such as Radix sort don't depend on comparison of two elements, though the three in questions are all comparison based.

There are more properties for sort such as online and recursion, but these five are often discussed when we see multiple sort algorithms.

Answer 2

Well. If you considered only the asymptotic time complexity $\mathcal{O}(\mbox{N log N})$, then there would be practically no difference between Quick and Heap sort. So both algorithms runtime is:

$\mbox{constant} \cdot \mbox{N log N}$

but, the constant may differ significantly and this is what makes a big difference. So, in practice, Quick sort is much more effective and requires much less comparisons than Heap sort (see e.g. here) - so the constant in the above expression for Quick sort is much smaller. That's why Quick sort is the one most used for general purpose..

Answer 3

I would assume that it is a combination of the following aspects:

1. The worst-case of quick sort happens very rarely (and can be detected/circumvented)
2. Heapsort has to swap more often
3. Subproblems of quick sort are independent of each other and can thus be solved in parallel

Answer 4

One thing that I haven't seen mentioned is the difference between the space complexities of quicksort and heapsort. An efficient version of quicksort would have O(logn) space, but heapsort is constant O(1) space since no recursion or additional space allocation of any kind is required. That would of course make heapsort more space efficient than merge sort as well. However, it's also worth noting that mergesort is the only stable sorting algorithm out of the 3.