Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Have you tried the Google? –  ladaghini Aug 10 '12 at 19:43
1  
You might find that the wiki articles on heapsort and quicksort answer your questions. –  JSchlather Aug 10 '12 at 19:43
    
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. –  copper.hat Aug 11 '12 at 19:55
    
@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 ? –  Geek Aug 11 '12 at 19:58
    
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. –  copper.hat Aug 11 '12 at 20:05
add comment

1 Answer

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

share|improve this answer
    
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 ? –  Geek Aug 11 '12 at 18:40
    
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 ? –  Geek Aug 11 '12 at 18:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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