How it works:

Heap Sort uses a heap data structure to sort elements. It first builds a max heap from the input array, then repeatedly extracts the maximum element from the heap and places it at the end of the sorted array. This process continues until all elements are sorted. Heap Sort is efficient and guarantees O(n log n) time complexity even in the worst case.

• Time Complexity : O(n log n)
• Space Complexity : O(1)
• Best Case : O(n log n)