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.

$\endgroup$
  • $\begingroup$ Look at intro sort, you will get the whole idea! $\endgroup$ – kelalaka Aug 25 at 20:02
  • 1
    $\begingroup$ Possible duplicate of Why is quicksort better than other sorting algorithms in practice? $\endgroup$ – ryan Sep 25 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 at 4:26
0
$\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..

$\endgroup$
  • 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 at 20:15
  • $\begingroup$ @kelalaka deleted too :-) $\endgroup$ – TMS Aug 25 at 20:36
  • $\begingroup$ @Evil I haven't said it's guaranteed... $\endgroup$ – TMS Aug 25 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 at 5:00
  • $\begingroup$ Do the working principles of both Quicksort and Heapsort have to do with it? $\endgroup$ – user529767 Aug 26 at 6:52
0
$\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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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