Heap Sort

heap_sort.js

//Create a sorted array (ascending) from a max heap
//Time Complexity: O(N log N)
//Space Complexity: O(1) because array is sorted in place
const heapSort = (arr, end) => {
  while(end > 0){
    let tmp = arr[end];
    arr[end] = arr[0];
    arr[0] = tmp;
    end -= 1;
    
    //siftDown is implemented in Building Heaps section below
    arr = siftDown(arr, 0, end)
  }
  
  return arr;
}

console.log(heapSort(arr, arr.length - 1))