Heap Sort — VisualAlgorithms Docs

How it works

Heap Sort first builds a max-heap from the array in O(n), then repeatedly swaps the root (the maximum) to the end of the array and sifts the new root down to restore the heap property, shrinking the heap by one each time.

Every extraction costs O(log n) and there are n of them, so the total is a guaranteed O(n log n) with no extra memory.

Implementation

      
 function heapSort(arr) {
  function siftDown(n, i) {
    let largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest !== i) {
      [arr[i], arr[largest]] = [arr[largest], arr[i]];
      siftDown(n, largest);
    }
  }
  for (let i = Math.floor(arr.length/2)-1; i >= 0; i--)
    siftDown(arr.length, i);
  for (let i = arr.length-1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    siftDown(i, 0);
  }
} def heap_sort(arr):
    def sift_down(n, i):
        largest, l, r = i, 2*i+1, 2*i+2
        if l < n and arr[l] > arr[largest]: largest = l
        if r < n and arr[r] > arr[largest]: largest = r
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            sift_down(n, largest)
    for i in range(len(arr)//2-1, -1, -1):
        sift_down(len(arr), i)
    for i in range(len(arr)-1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        sift_down(i, 0) void heapSort(vector<int>& arr) {
  auto siftDown = [&](int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) {
      swap(arr[i], arr[largest]);
      // recurse
    }
  };
  int n = arr.size();
  for (int i = n/2-1; i >= 0; i--) siftDown(n, i);
  for (int i = n-1; i > 0; i--) {
    swap(arr[0], arr[i]);
    siftDown(i, 0);
  }
} void HeapSort(int[] arr) {
  void SiftDown(int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) {
      (arr[i], arr[largest]) = (arr[largest], arr[i]);
      SiftDown(n, largest);
    }
  }
  for (int i = arr.Length/2-1; i >= 0; i--)
    SiftDown(arr.Length, i);
  for (int i = arr.Length-1; i > 0; i--) {
    (arr[0], arr[i]) = (arr[i], arr[0]);
    SiftDown(i, 0);
  }
} void siftDown(int arr[], int n, int i) {
  int largest = i, l = 2*i+1, r = 2*i+2;
  if (l < n && arr[l] > arr[largest]) largest = l;
  if (r < n && arr[r] > arr[largest]) largest = r;
  if (largest != i) {
    int t = arr[i]; arr[i] = arr[largest]; arr[largest] = t;
    siftDown(arr, n, largest);
  }
}
void heapSort(int arr[], int n) {
  for (int i = n/2-1; i >= 0; i--) siftDown(arr,n,i);
  for (int i = n-1; i > 0; i--) {
    int t = arr[0]; arr[0] = arr[i]; arr[i] = t;
    siftDown(arr, i, 0);
  }
} 

Advantages

Guaranteed O(n log n) worst case with O(1) extra memory.
No recursion and no pathological inputs.

Disadvantages

Not stable.
Poor cache locality from the jumpy parent/child index pattern makes it slower than Quick Sort in practice.

When to use it

Use it when you need a hard worst-case bound and cannot spare auxiliary memory — for example as the fallback inside IntroSort.