0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Look at intro sort, you will get the whole idea! $\endgroup$
    – kelalaka
    Aug 25, 2019 at 20:02
  • 1
    $\begingroup$ Possible duplicate of Why is quicksort better than other sorting algorithms in practice? $\endgroup$
    – ryan
    Sep 25, 2019 at 22:52
  • $\begingroup$ "But I couldn't figure out the difference between quick sort and heap sort." You said "Merge sort and Heap sort algorithms take O(N log N) time in worst-case where Quicksort takes O(N^2)". Don't you answer this question by yourself? "Which algorithm is preferable for sorting at any time?" This question would be opinion-based or too broad. $\endgroup$
    – xskxzr
    Sep 26, 2019 at 4:26
  • $\begingroup$ Try sorting a linked list with all three listed algorithms. You'll probably notice that you have been missing something! $\endgroup$
    – Erwan Legrand
    Feb 14, 2020 at 15:29
  • $\begingroup$ Also, have you ever heard of external sorting? Now realize that access to main memory is two orders of magnitude slower than access to L1 cache. Got some interesting thoughts? $\endgroup$
    – Erwan Legrand
    Feb 14, 2020 at 15:35

4 Answers 4

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Quicksort is not guaranteed NlogN, as stated in the question, and the follow up is to consider why QS is used so often. $\endgroup$
    – Evil
    Aug 25, 2019 at 20:15
  • $\begingroup$ @kelalaka deleted too :-) $\endgroup$
    – Tomas
    Aug 25, 2019 at 20:36
  • $\begingroup$ @Evil I haven't said it's guaranteed... $\endgroup$
    – Tomas
    Aug 25, 2019 at 20:39
  • $\begingroup$ Ok, I mean when you stated that asymptotics are equal, it is not fully true, if it were about Merge and Heap, it would be proper. If you stated that Quicksort could avoid the worst case with additional technique like median of medians or that Quicksort rarely runs into the worst case it would also be proper. I have understood your first paragraph as if Quicksort runs in NlogN time. It is true that constant is smaller and very often Quicksort outperforms other algorithms. Without explanation it looks wrong to me. $\endgroup$
    – Evil
    Aug 26, 2019 at 5:00
  • $\begingroup$ Do the working principles of both Quicksort and Heapsort have to do with it? $\endgroup$
    – user529767
    Aug 26, 2019 at 6:52
1
$\begingroup$

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
Improve this answer
$\endgroup$
2
  • $\begingroup$ Quick sort's worst case actually happens very often! $\endgroup$
    – Erwan Legrand
    Feb 14, 2020 at 15:34
  • $\begingroup$ Would you say "happens very rarely (if the pivot element is chosen correctly" is correct? $\endgroup$
    – oerpli
    Feb 15, 2020 at 6:46
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.