Using heap sort

Heap sort requires us to build a heap from a given list of elements and then continuously checks the heap property so that the whole heap remains sorted all the time. Unlike a regular heap where we stop checking the heap property once the newly inserted value satisfies the conditions, we continue to do so for the next elements during the heap sort implementation. The pseudocode of the heap sort looks like this:

Heapsort(A as array) 
    BuildHeap(A) 
    for i = n-1 to 0 
        swap(A[0], A[i]) 
        n = n - 1 
        Heapify(A, 0) 

BuildHeap(A as array) 
    n = elements_in(A) 
    for i = floor(n/2) to 0 
        Heapify(A,i) 

Heapify(A as array, i as int) 
    left = 2i+1 
    right = 2i+2 
    max = i 

    if (left <= n) and (A[left] > A[i]) 
        max = left 

    if (right<=n) and (A[right] > A[max]) 
        max = right 

    if (max != i) 
        swap(A...