Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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 though.

share|cite|improve this answer

Your Answer


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.