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

1

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

  • 0
    the first step of heap sort is a heap out of the data using the Build-Max-Heap funtion . The Build-Max-Heap function converts an array A which stores a complete binary tree with n nodes to a max-heap by repeatedly using Max-Heapify in a bottom up manner . And Max-Heapify(A, i) has a recursive call to itself. So the heap Sort is also recursive in a sense or am I issing something here ?2012-08-11
  • 0
    Also can u explain what you mean by "Most importantly, heapsort has rather dismal memory access patterns,". Why you are calling the memory access pattern dismal ?2012-08-11