Heap sort

Hard TimeO(n log n) SpaceO(1)

Given an array arr of numbers, sort it into ascending order in place, with no second array: the values still to be placed and the ones already finished share the array the input came in. The cost is the same whatever the input, worst case included.

Examples

Example 1

Input
arr = [5, 3, 8, 1, 9, 2]
Output
[1,2,3,5,8,9]
The same six values, ascending, in the array they arrived in.

Example 2

Input
arr = [9, 8, 7, 6]
Output
[6,7,8,9]
Exactly reversed on the way in, and it costs no more than any other order.

The Code

function heapSort(arr) {
  const n = arr.length;
  function siftDown(start, end) {
    let root = start;
    while (root * 2 + 1 <= end) {
      const child = root * 2 + 1;
      let swap = root;
      if (arr[swap] < arr[child]) swap = child;
      if (child + 1 <= end && arr[swap] < arr[child + 1]) swap = child + 1;
      if (swap === root) return;
      const temp = arr[root];
      arr[root] = arr[swap];
      arr[swap] = temp;
      root = swap;
    }
  }
  for (let start = Math.floor(n / 2) - 1; start >= 0; start--) {
    siftDown(start, n - 1);
  }
  for (let end = n - 1; end > 0; end--) {
    const temp = arr[0];
    arr[0] = arr[end];
    arr[end] = temp;
    siftDown(0, end - 1);
  }
  return arr;
}
heapSort([5, 3, 8, 1, 9, 2]);
Done

The first 33 calls, of 35. This one does not fit on a page.

Step through heapSort([5, 3, 8, 1, 9, 2]) call by call

More like this

All sorting examples (8) →