Talks -Algorithmic ideas, engineering tricks, and trivia behind CPython's new sorting algorithm

From the creator

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

Published 2023-06-02 · Watch on YouTube ↗
Availability and playback restrictions are controlled by the original channel.