0
$\begingroup$

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.

1 Answers 1

0

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.