Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to achieve O(n log n) time complexity. It's an in-place sorting algorithm, meaning it requires only O(1) additional space (or O(log n) for the recursion stack if implemented recursively). The algorithm consists of two main phases. First, the input array is converted into a max-heap. A max-heap is a complete binary tree where the value of each node is greater than or equal to the value of its children. This 'heapify' process can be done in O(n) time. The largest element in the array is now at the root of the heap (index 0). In the second phase, we repeatedly extract the maximum element from the heap and build the sorted array. We swap the root element (the maximum) with the last element of the heap. We then reduce the size of the heap by one and call 'heapify' on the root again to restore the max-heap property. This process is repeated until the heap is empty. The elements we swapped to the end of the array naturally form a sorted sequence in reverse order. Because each of the `n-1` extraction operations involves a call to heapify which takes O(log n) time, this phase takes O(n log n) time, which is the dominant complexity.