Algorithm

Heap Sort Algorithm:

1. Start with an unsorted array.
2. Build a Max Heap from the array:
   1. Ensure the heap property is satisfied at every node.
   2. Start from the last non-leaf node and heapify all parent nodes.
3. Extract the root (largest element) of the heap and place it at the end of the array.
4. Restore the heap property for the remaining unsorted portion of the array.
5. Repeat the process until the entire array is sorted.

Example:

Fig. 1: Iteration by Iteration Visualization of Heap Sort

Note: Heap Sort efficiently uses a binary heap to sort elements, making it suitable for in-place sorting.