Seth.

Heap Sort - Technical Overview

1. Algorithm Description: Heap Sort is a comparison-based sorting algorithm. It is based on a binary heap data structure, and is an in-place sorting algorithm.

2. Steps of Heap Sort:

• Build a max heap from the input array.
• Extract the maximum element from the heap (the root).
• Swap it with the last element in the array.
• Reduce the size of the heap and heapify the root.
• Repeat the process until the array is sorted.

3. Time Complexity: O(n log n) in all cases (worst, average, best).

4. Space Complexity: O(1), as it operates in-place.

5. Stability: Heap Sort is not a stable algorithm because it does not maintain the relative order of equal elements.