Overview
Heap Sort first arranges the array into a heap. It then swaps the root with the end of the unsorted region and restores the heap property until the array is sorted.
FoundationSource checked
Heap Sort
Sorts a list by building a heap and repeatedly removing the highest-priority item.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Sorting
- Difficulty
- Intermediate
- Family
- Heap Based Sort
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Heapsort
Core Concepts
binary heapheapifyextract rootin-place sorting
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(1)
When to Use
- Use it when in-place O(n log n) sorting with a strong worst-case bound is needed.
- Use it when stable ordering is not required.
- Use it as a fallback inside introspective sorting.
When Not to Use
- Avoid it when stability matters.
- Avoid it when a cache-friendly average-case sort is more important than worst-case guarantees.
What It Does
- Builds a heap from the input
- Moves the largest remaining value into place
Use Cases
- Sorting with predictable worst-case time
- In-place array sorting
- Teaching heap behavior
Inputs
- Array of comparable values
Outputs
- Sorted array
Pseudocode
- 1.Build a max heap from the array
- 2.Swap the heap root with the last unsorted item
- 3.Shrink the heap boundary
- 4.Restore the heap property
- 5.Repeat until the heap is empty
Canonical Example
- Input
- array = [4, 10, 3, 5]
- Output
- [3, 4, 5, 10]
- Explanation
- The array is heapified, then the largest remaining value is repeatedly moved to the sorted suffix.
Implementation Notes
- Build the heap bottom-up before extraction.
- After each root swap, shrink the heap before sifting down.
- Test with duplicate keys to make stability expectations explicit.
Common Pitfalls
- Mixing heap size with full array length after each extraction.
- Using the wrong child index formulas for zero-based arrays.
- Forgetting that heap sort is not stable.
Interactive Mechanism Walkthrough
Array Partition & Ordering TraceShow the heap tree and the sorted suffix growing from the end.
38[0]
14[1]
52[2]
23[3]
61[4]
19[5]
44[6]
29[7]
Step 1 of 5: Build a max heap from the array
heap-arrayNotes
Heap sort trades some practical locality for an in-place worst-case O(n log n) guarantee.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Heap Sort invariants, recurrences, relaxation rules, or asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Has variantsSmoothsort
Sorting · Extended
Smoothsort is a heap-sort variant using Leonardo heaps to exploit existing order.
Compare with thisAlternative toQuick Sort
Sorting · Foundation
Heap Sort avoids Quick Sort's worst-case partition behavior but is usually less cache-friendly.
Compare with thisRelationships
View full relationship pageUsesHeap
Heap Sort repeatedly extracts the maximum or minimum from a heap.
Alternative toQuick Sort
Heap Sort avoids Quick Sort's worst-case partition behavior but is usually less cache-friendly.
Related Algorithms
Tags
Comparison SortPriority QueueIn PlaceClassic