What is the running time of \(\textsc{Heapsort}\) on an array \(A\) of length \(n\) that is already sorted in increasing order? What about decreasing order?
To analyze heapsort’s performance on sorted inputs, we need to consider two phases separately: building the heap and extracting elements. Unlike quicksort, which performs dramatically differently on sorted versus unsorted data, heapsort’s behavior is more uniform.
Running time for increasing order
When the input array is sorted in increasing order (e.g., \(\langle 1, 2, 3, 4, 5 \rangle\)), it represents the worst possible configuration for a max-heap. The smallest element sits at the root position, and building the max-heap requires extensive restructuring.
During the \(\textsc{Build-Max-Heap}\) phase, we still need \(O(n)\) time regardless of the input order (this is always true for building a heap). However, the structure we create is quite different from what we started with.
In the sorting phase, each call to \(\textsc{Max-Heapify}\) after swapping the root to the end must traverse nearly the full height of the heap. For an array sorted in increasing order, after we build the max-heap, the largest element is at the root. When we remove it and call \(\textsc{Max-Heapify}\), the new root (which came from the last position) is typically much smaller than its children, so it must sink all the way down to a leaf position.
This pattern repeats for all \(n-1\) iterations. Each \(\textsc{Max-Heapify}\) operation takes \(O(\lg n)\) time in the worst case. Therefore, the total running time is \(O(n \lg n)\).
Running time for decreasing order
When the input array is sorted in decreasing order (e.g., \(\langle 5, 4, 3, 2, 1 \rangle\)), it already satisfies the max-heap property. The largest element is at position 1, and each parent is larger than its children.
During \(\textsc{Build-Max-Heap}\), very little work is needed since the array already forms a valid max-heap. However, this doesn’t help us in the sorting phase.
In the sorting phase, we still perform \(n-1\) iterations, each involving a swap and a call to \(\textsc{Max-Heapify}\). Even though we started with a perfect max-heap, after each swap we place a small element at the root, which must sink down through the heap. This still requires \(O(\lg n)\) time per iteration.
Therefore, the running time is still \(O(n \lg n)\).