Heap Sort

Heap sort turns the array into a max-heap — a complete binary tree, stored in the array itself, where every parent is at least as large as its children. That puts the maximum at the root. Swap the root to the end, shrink the heap, repair it, and repeat: each step extracts the next-largest value into its final place. It runs in guaranteed O(n log n) using no extra memory.

The array is the tree

No pointers needed: in a 0-indexed array, node i's children are at 2i+1 and 2i+2, and its parent is at (i-1)/2. Sift down is the core operation — to repair the heap after the top changes, sink the new root past whichever child is larger, again and again, until the heap property holds.

1. 1Build a max-heap by sifting down every internal node, from the last one up to the root.
2. 2Swap the root (the maximum) with the last element of the heap.
3. 3Shrink the heap by one — the swapped-out maximum is now in its final sorted position.
4. 4Sift down the new root to restore the max-heap.
5. 5Repeat until the heap holds one element.

function heapSort(arr) {
  const n = arr.length;
  const siftDown = (i, size) => {
    while (true) {
      let big = i, l = 2 * i + 1, r = 2 * i + 2;
      if (l < size && arr[l] > arr[big]) big = l;
      if (r < size && arr[r] > arr[big]) big = r;
      if (big === i) break;
      [arr[i], arr[big]] = [arr[big], arr[i]];
      i = big;
    }
  };
  for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(i, n); // build heap
  for (let end = n - 1; end > 0; end--) {
    [arr[0], arr[end]] = [arr[end], arr[0]]; // max to the end
    siftDown(0, end);                         // repair the rest
  }
  return arr;
}