Still work in progress …

Part I Heapify …

Part II sort and heapify

We start swapping values and heapify each time starting from 0 to the length of i

function heapSort(arr) {

    function maxHeapify(arr, i, N) {
        var leftChild = i * 2 + 1;
        var rightChild = i * 2 + 2;
        var largest = i;
    
        if(leftChild < N && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }
    
        if(rightChild < N && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }
    
        if(largest != i) {
            var temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            maxHeapify(arr, largest, N);
        }
    }
    
    // CREATE A HEAP
    for(var i = parseInt(arr.length / 2 - 1); i >= 0; i--) {
        maxHeapify(arr, i, arr.length);
    }
    
    console.log("heap represented in array: ", arr);
    
    // SORT THE ARRAY
    for(var i =  arr.length - 1; i >= 0; i --) {
        var temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
    
        maxHeapify(arr, 0, i);
    }
}

const arr = [4, 6, 3, 2, 9, 1];
heapSort(arr);

console.log("sorted array:", arr);