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?
$\endgroup$ 51 Answer
$\begingroup$Heapsort works in-place too (and with slightly lower administrative space needed, because it is not recursive).
The constant factors are very dependent on implementation details and hardware characteristics, especially on the performance parameters of the memory hierarchy. Most importantly, heapsort has rather dismal memory access patterns, so on a real computer it will typically lose to quicksort for large $n$s independently of any mathematical analysis that counts primitive operations and assume they all cost the same.
(It also helps quicksort in practice that it is easily modified to switch to more efficient strategies when the size of the subproblems becomes small, which can increase the constant factors considerably over a "vanilla" quicksort. Heapsort has no way to do that).
$\endgroup$ 2
