64
34
25
12
22
11
90
0
1
2
3
4
5
6
Starting Heap Sort. First we build a max-heap from the array.
Presets:
Size:
Timeline Progress:
0%Step 1 / 40
Comparisons
0
Swaps / Actions
0
Speed:
Shortcuts: Space Play • ←/→ Step • R Reset • M Sound • Z Focus
Implementation Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function heapSort(arr: number[]): number[] {
const n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, i, 0);
}
return arr;
}
function heapify(arr: number[], n: number, i: number): void {
let largest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest);
}
}Complexity Analysis
Best Case
O(n log n)
Average Case
O(n log n)
Worst Case
O(n log n)
Space
O(1)
Color Legend
Unsorted
Comparing
Swapping
Sorted
Heap Sort first builds a max-heap from the array, then repeatedly extracts the maximum element from the heap and places it at the end of the array. It achieves O(n log n) in all cases and sorts in-place. While it has good theoretical guarantees, it has poor cache performance compared to Quick Sort due to non-sequential memory access patterns.