Watch heap sort build a max-heap, then eject the maximum to the end one bar at a time. O(n log n) guaranteed with O(1) extra space — and why it is still rarely used.
Algorithm
Array
Comparisons
0
Swaps/writes
0
Step
0/665
Reads
0
Aux memory
0
Call depth
1/1
Slow the speed and use Step to match the pseudocode highlight with the bar colors. Grey bars are positions already ejected from the heap and finalized.
Pseudocode
build max-heap (siftDown n/2→0)
for end ← n−1 down to 1
swap a[0] ↔ a[end] // 최댓값 확정
siftDown(0, end)
// child = 2·i+1, 2·i+2 중 큰 쪽과 비교
// 부모 < 자식이면 교환하며 내려감
Time complexity
| Best | O(n log n) |
|---|---|
| Average | O(n log n) |
| Worst | O(n log n) |
| Space | O(1) |
| Stable | No |
Heap sort treats the array as a complete binary tree (children of i are 2i+1, 2i+2), rearranges it into a max-heap where every parent beats its children, then swaps the root maximum to the end and re-heapifies the remainder.
Heap construction is O(n) and each extraction costs O(log n), giving a guaranteed O(n log n) with O(1) extra space. It loses to quicksort in practice because parent-child jumps wreck cache locality — but it remains the backbone of priority queues. Sorting Visualizer