Question presented to candidate:
"Python's sorted() and list.sort() use an algorithm called Timsort. How does it work, why is it so fast on real-world data, and why is it guaranteed to be stable? What is its complexity?"
What a strong answer should cover:
- Timsort is a hybrid, adaptive, stable merge sort designed by Tim Peters for CPython (2002): it exploits order that already exists in the data
- It scans for natural runs (non-descending, or strictly descending which it reverses in place), extends short runs to minrun (32-64 elements) with binary insertion sort, and merges neighbouring runs
- The merge order keeps runs balanced; since CPython 3.11 it follows the powersort rule (bpo-34561) instead of the original stack invariants; merges use galloping when one run keeps winning
- Complexity: O(n log n) worst case, O(n) best case (about n - 1 comparisons on sorted or reversed input), O(n) extra memory for merging
- Stability comes from never moving an element past an equal one: runs are only reversed when strictly descending, and merges take from the left run on ties; that enables multi-pass sorts by several keys
- Only
<is ever used, and the key function is called exactly once per element
Code / implementation expected: Optional — counting comparisons on sorted vs shuffled data, or sketching run detection and merging.