**Algorithm for Heap Sort **

Step 1: [Build Heap H]
Repeat for I= 0 to N-1
CALL Insert_Heap(ARR, N, ARR[I])
[END OF LOOP]
Step 2: (Repeatedly delete the root element)
Repeat while N > 0
CALL Delete_Heap(ARR, N, VAL)
SET N= N+1
[END OF LOOP]
Step 3: END

**How Heap Sort Works**

- Initially on receiving an unsorted list, the first step in heap sort is to create a Heap data structure (Max-Heap or Min-Heap).
- Once heap is built, the first element of the Heap is either largest or smallest (depending upon Max-Heap or Min-Heap), so we put the first element of the heap in our array.
- Then we again make heap using the remaining elements, to again pick the first element of the heap and put it into the array.
- We keep on doing the same repeatedly until we have the complete sorted list in our array.