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.

wanted to ask if someone can confirm me that there is no initial configuration of an array A of length n that will result in linear running time of heapsort, because the running time of heapsort on an array A of length n regardless of the initial configuration is O (nlgn) because even though it is already sorted or not, it will be transformed back into a heap and sorted again.

Is my assumption right?

Thanks, f.g.

share|improve this question

1 Answer 1

up vote 0 down vote accepted

Yes your assumption is right, already the extraction phase of heapsort takes $n\log n$ time¸ regardless. See also the Wikipedia article, in particularly where is mentions smoothsort. Note also that heapsort does not allow stable sorting (not perturbing the order among elements whose keys comapre equal, but may be distinguishable otherwise); this is an indication that the original order among elements is not used in any way.

For other questions of this sort (no pun intended) you may want to prefer cs.stackexchange.com though.

share|improve this answer

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.