The best-, average-, and worst case time complexity of Heapsort for $n$ distinct keys are all $\Theta(n \lg n)$.

What are the worst-case inputs for heapsort?


1 Answer 1


Please check the paper@arXiv2015: A Complete Worst-Case Analysis of Heapsort by M. A. Suchenek.

This paper gives a rather involved lower bound; see Abstract and Theorem 12.2 on page 94.

To the specific question,

Example of a 500-node worst-case array for Heapsort, created by my Java program, is included in Appendix A.3 page 110.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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