Algorithms and Data Structures · Senior · Question 31 of 75
Why does Timsort perform so well on real-world data?
- 1It switches to counting sort for numbers
- ✓Correct answer: It detects existing sorted runs and merges them
- 3It sorts in parallel on all CPU cores
Explanation
Real data is often partially ordered: appended logs, mostly sorted lists. Timsort finds ascending (or reversed descending) runs, extends short ones with insertion sort and merges them with galloping, approaching O(n) on nearly sorted input.