Worst case time complexity of heap sort for n elements?

Concept

Heap sort runs in two phases: build a binary heap from the n inputs, then repeatedly remove the root and restore the heap. The governing fact is that a binary heap of n nodes has height ⌊log n⌋, so any single sift-down (heapify) costs O(log n). A bound that holds even for the most adversarial input is the algorithm's worst-case time complexity.

Application

1. Build phase: constructing the heap by sifting down from the lowest internal node up to the root costs O(n) (a tighter bound than the naive n·log n).

2. Selection phase: remove the maximum (the root), move it to the end, and sift the new root down to restore the heap. One restore costs O(log n).

3. This remove-and-restore is repeated for all n elements, giving n · O(log n) = O(n log n).

4. Total = O(n) + O(n log n) = O(n log n).

Cross-check

The heap's height is logarithmic regardless of input order, so no arrangement forces a sift-down longer than log n; therefore the best, average, and worst cases are all O(n log n). This also respects the Ω(n log n) lower bound that every comparison-based sort must obey, so a linear or logarithmic total is unattainable, and the heap structure prevents the quadratic degradation seen in elementary sorts.