Recall that Heap Sort consists of two main phases: building a max-heap from the input array and repeatedly extracting the maximum element to sort the array. Focus on the heap construction phase first.

Consider the worst-case scenario for heap construction. How many comparisons are made when building a heap from an arbitrary input array? Use the concept of "heapify" operations and analyze the height of the heap.

Prove that the total number of comparisons in the heap construction phase is O(n). Then, analyze the extraction phase, where each of the n extractions involves a heapify operation that takes O(log n) time. Combine these to establish the overall O(n log n) time complexity.