← Back to the sorting page
Heapsort & Hybrid Sorts (Timsort, Introsort)
Heapsort gives worst-case O(n log n) in place; real libraries blend algorithms — Timsort (merge + insertion) and introsort (quick + heap + insertion).
What to know
- Heapsort: build a max-heap in O(n), then repeatedly swap the root to the back.
- Timsort detects natural runs and merges them with galloping — O(n) on sorted input.
- Introsort switches quicksort → heapsort past 2·log n recursion depth.
In the wild: Python sorted()/list.sort, Java Arrays.sort(objects), C++ std::sort, V8 Array.sort.
Algorithms to reach for
Heapsort
O(n log n)Guaranteed O(n log n), O(1) space, adversary-proof
Timsort
O(n) – O(n log n)Exploit existing order in real-world data
Introsort
O(n log n)Quicksort speed with a hard worst-case cap
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.