Description
Writing a sorting function is easy - coding a fast and reliable reference implementation less so. In this talk, I tell the story behind CPython's latest updates of the list sort function.
Aims: entertain people with twists of history and algorithmic puzzles, which tell a lovely story of how a seemingly useless piece of theory lead to the fastest and most elegant solution of a practical challenge.
Target audience: geeks believing in the power of solid algorithmic thinking; programmers interested in engineering performance-critical code; all Python enthusiast curious about what makes (sorting lists in) Python fast.
Content: After using Quicksort for a long while, Tim Peters invented Timsort, a clever Mergesort variant, for the CPython reference implementation of Python. Timsort is both effective in Python and a popular export product: it is used in many languages and frameworks, notably OpenJDK, the Android runtime, and the V8 JavaScript engine.
Despite this success, algorithms researchers eventually pinpointed two flaws in Timsort's underlying algorithm: The first could lead to a stack overflow in CPython (and Java); although it has meanwhile been fixed, it is curious that 10 years of widespread use didn't bring it to surface. The second flaw is related to performance: the order in which detected sorted segments, the “runs” in the input, are merged, can be 50% more costly than necessary. Based on ideas from the little known puzzle of optimal alphabetic trees, the Powersort merge policy finds nearly optimal merging orders with negligible overhead, and is now (Python 3.11.0) part of the CPython implementation.