Heap Sort

Time Complexity:

• Best: O(n log n)
• Average: O(n log n)
• Worst: O(n log n)

Space Complexity: O(1)

Stable: No

In-Place: Yes

Phase 1: Build Max Heap

Transform the array into a max heap where every parent is greater than or equal to its children. Start from the last non-leaf node and heapify downwards.

Phase 2: Extract Maximum

Repeatedly swap the root (maximum element) with the last element of the heap, reduce heap size, and heapify the root to maintain heap property.