mastorna.it
IT

Sorting algorithms · 4/7

Heapsort

Builds a max heap and moves maxima to the end.

Average timeΘ(n log n) SpaceΘ(1) StableNo In placeYes

How it works

The root holds the maximum. Swap it with the active end, shrink the heap, and restore the heap property.

Invariant: After each extraction the suffix is final and sorted, while the prefix is a max heap.

Step-by-step visualization

Each bar represents one element. Colors identify compared elements, the pivot or key, the final region and the active range.

Use 2 to 16 values. This visualizer accepts values from 0 to 999.

Comparisons
0
Writes
0
Swaps
0
Pass / level
0
active comparison pivot / key final

Pseudocode linked to the visualization

  1. buildMaxHeap(A)
  2. for end ← n − 1 downto 1
  3. swap A[0], A[end]
  4. siftDown(A, 0, end)
  5. siftDown(A, root, end)
  6. child ← 2 · root + 1
  7. choose the larger child
  8. if child > root: swap and continue

The highlighted line corresponds to the operation described by the visualizer. Index-management details are intentionally simplified.

Complexity analysis

Best caseΘ(n log n)

The standard extraction phase performs n−1 heap repairs, Θ(n log n).

Average caseΘ(n log n)

Build-heap is Θ(n); Θ(n log n) extraction dominates.

Worst caseΘ(n log n)

Heap height is always Θ(log n), so worst time stays Θ(n log n).

Auxiliary spaceΘ(1)

The iterative form uses Θ(1) auxiliary space. Long-distance swaps destroy stability.

Properties at a glance

Unstable

Stability concerns the relative order of elements with equal keys.

In place

This classification refers to the version shown on this page.

When to use it and what to avoid

A good choice when…

Useful for a Θ(n log n) guarantee with constant auxiliary space.

Common mistake

Bottom-up build-heap is Θ(n); n separate insertions would be Θ(n log n).