# Heapsort
**URL:** https://thecodex.expert/coding/algorithms/sorting/heapsort/
**Type:** algorithm | **Confidence:** high | **Verified:** 2026-06-01

## CANONICAL DEFINITION
Heapsort is a comparison-based in-place sorting algorithm that first builds a max-heap from the input array, then repeatedly extracts the maximum element to produce a sorted sequence — achieving Theta(n log n) time in all cases with O(1) auxiliary space.

## COMPLEXITY
- best: Theta(n log n)
- average: Theta(n log n)
- worst: Theta(n log n)
- space: O(1)
- stability: not stable

## REQUIRES
data-structures/heaps, algorithms/sorting

## ENABLES
algorithms/sorting/insertion-sort

## SOURCES
- CLRS 4th ed. Ch.6
- Williams 1964 CACM 7(6)
- Floyd 1964 CACM 7(12)
- Fredman & Tarjan 1987 JACM 34(3)

*The Codex Coding — thecodex.expert/coding/ — Free forever*