Production hybrids · Advanced
Introsort
Start with Quicksort, switch to Heap Sort if recursion gets risky, and finish tiny ranges with insertion.
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Space
- O(log n)
- Stability
- Not stable
- Memory model
- In-place
How it builds order
- Partition like Quicksort.
- Decrease the depth budget.
- Use Heap Sort when the budget reaches zero.
- Use Insertion Sort for tiny ranges.
Why it works
Quicksort supplies strong average behavior; the heap fallback caps the worst case; insertion reduces overhead on small ranges.
Watch for: The depth budget prevents repeatedly bad partitions from reaching quadratic time.
The interactive version of this page adds the full trace, synchronized pseudocode, practice decisions, input experiments, and mastery review.