Heap Sort

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

Size48
ComparingSwap/writePivot/keyReadSorted
Speed50×

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

BestO(n log n)
AverageO(n log n)
WorstO(n log n)
SpaceO(1)
StableNo

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

Frequently asked questions

What is a heap?
A complete binary tree where each parent is larger than its children (max-heap). In an array, node i's children live at 2i+1 and 2i+2 — no pointers needed.
Where is heap sort actually used?
Memory-constrained systems, worst-case-guarantee contexts, top-K selection (like C++ partial_sort), and inside priority queue implementations.

Other algorithms