0
$\begingroup$

Heap Sort has complexity $\mathcal{O}(n\lg(n))$ and Quick Sort with some tuning (choosing the pivot in a random order) on average also sorts in $\mathcal{O}(n\lg(n))$ and both of these are tight upper bounds.

1) So between the two algorithms which one should be used and why? Which one has smaller constant factors?

2) I know quick sort sorts in place . What about memory requirements for Heap sort?

  • 0
    Have you tried the Google?2012-08-10
  • 1
    You might find that the wiki articles on [heapsort](http://en.wikipedia.org/wiki/Heapsort) and [quicksort](http://en.wikipedia.org/wiki/Quicksort) answer your questions.2012-08-10
  • 0
    This is hard to answer because you are getting into implementation details, and input characterization. I believe the general opinion is that quicksort is generally better, but has potential for significant slowdown. Regarding memory, I do not know, but keep in mind that quicksort is typically recursive.2012-08-11
  • 0
    @copper.hat Please see my first comment to Henning Makholm . The way I see it is that heap sort is also recursive indirectly . Am I missing some thing ?2012-08-11
  • 0
    You are not missing anything. Some implementations of heapsort use tail recursion, but it is unnecessary, and can be removed. I would presume that most compilers optimize for tail recursion.2012-08-11

1 Answers 1