Algorithmic ideas, engineering tricks, and trivia behind CPython's new sorting algorithm
summary
Describes CPython’s list.sort evolution from Quicksort to TimSort (a mergesort variant by Tim Peters), explains two algorithmic flaws found in TimSort (a stack overflow bug and suboptimal run-merge ordering), and shows how the Powersort merge policy—inspired by optimal alphabetic tree puzzles—reduces merge cost and was integrated into CPython 3.11.0.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:55Outline
- 3:04Stable Sorting
- 4:03CPython Sorting History
- 9:18Timsort merge policy (original)
- 12:02Invariant trouble
- 13:33Timsort merge policy (patched)
- 14:11Timsort bad case
- 15:28Merge policies from first principles
- 17:51Mergesort meets Binary Search Trees
- 22:40Run-Boundary Powers are Local
- 25:58Some performance data
- 26:40Bonus: Multiway powersort
- 27:38Conclusion
related talks
57mPython's other collection types and algorithms
20mList me your virtues
01h 18mPython 103: Mmmm... Understanding Python's Memory Model, Mutability, and Methods
25mPython Heaps-ters
24mCS101 Intro to Computational Complexity: The Sorting Problem
01h 18mPython 103: Mmmm... Understanding Python's Memory Model, Mutability, and Methods
52mPython Tips, Tricks, and Idioms
01h 07mWhat Does It All Really Mean