HEAP_SORT(K,N)
[K is the array of created heap and N is the total number of elements in the array]

1. [Create the Initial Heap]
Call CREATE_HEAP(K,N).
2. [Perform Sort]
Repeat thru step 7 for
Q <-- N,N-1,….2.

3. [Interchange record]

KEY <-- K[Q]
K[Q] <-- K[1].

4. [Initialize pass]

I <-- 1
J <-- I * 2.

5. [Find proper place for new record]

Repeat while J > Q & (KEY < K[J] or KEY < K[J+1])
if (J+1=Q)
if (K[J] > KEY)
K[I] <-- K[J]
I <-- J
J <-- I * 2
else
exit the loop and goto step 6.

else if (K[I] > K[J+1]
K[I] <-- K[J]
I <-- J
J <-- I * 2
else
K[I] <-- K[J+1]
I <-- J+1
J <-- I * 2.

7. [Copy record into its proper place]
K[I] <-- KEY

8. [FINISH]
return.