Production hybrids · Advanced
Timsort
Find natural ordered runs, extend short ones, and merge them while preserving stability.
- Best
- O(n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Space
- O(n)
- Stability
- Stable
- Memory model
- Uses auxiliary storage
How it builds order
- Detect ascending or descending runs.
- Reverse descending runs and extend short runs with insertion.
- Maintain a safe run stack.
- Stably merge neighboring runs.
Why it works
Natural runs capture existing order; stable merging combines them with the same guarantee as Merge Sort.
Watch for: Runs are the unit of work; existing order reduces how much merging is needed.
The interactive version of this page adds the full trace, synchronized pseudocode, practice decisions, input experiments, and mastery review.