Heap Sort

sorting

Click Generate New or press Play

Step 1 / 1

Ready

Speed

Builds a max heap from the array, then repeatedly extracts the maximum element to build the sorted array.

Time Complexity

Best

\mathrm{O}\left(n \log n\right)

Avg

\mathrm{O}\left(n \log n\right)

Worst

\mathrm{O}\left(n \log n\right)

Max Operations

Worst-case bound

2n \cdot \log_2(n)

Used for efficiency calculation in Stats Panel

Space Complexity

Aux

\mathrm{O}\left(\log n\right)

Recursive heapify — call stack depth = tree height

Pseudocode

1buildMaxHeap(A)

2heapify(i): compare node with children

3if child > node: swap and recurse

4max heap ready

5for i = n-1 downto 1:

6swap(A[0], A[i])

7heapify(0, i)