heapsort.js

const swap = (array, a, b) => {
  let tempa = array[a];
  array[a] = array[b];
  array[b] = tempa;
}

const maxheap = (array, index) => {
  const parenty = i => Math.ceil(i/2);
  const lefty = i => 2*i;
  const righty = i => 2*i + 1;

  const left = array[lefty(index)];
  const right = array[righty(index)];

  let largest = index;

  if(lefty(index) < array.length && array[index] < left) {
    largest = lefty(index);
  } else if(righty(index) < array.length && array[index] < right) {
    largest = righty(index);
  }

  if(largest !== index) {
    swap(array, largest, index);
    maxheap(array, largest);
  }
}

const treeify = array => {
  const len = Math.floor(array.length / 2) - 1;

  for(let i = len; i >= 0; i--){
    maxheap(array, i);
  }

  return array;
};

const heapsort = (array, sorted) => {
  const heaped = treeify(array);
  if(!array.length){
    return sorted;
  }
  sorted.unshift(array.shift());
  
  return heapsort(array, sorted);
};