Start
Type of event
Hybrid
Place/room
Lecture Hall 3, Campus 1 Griebnitzsee, 14482 Potsdam
and via tele-TASK/Zoom
Price
free
Quicksort, Timsort, Powersort - Algorithmic ideas, engineering tricks, and trivia behind CPython’s new sorting algorithm
- Lecturer: Prof. Sebastian Wild, Algorithms Group, Department of Computer Science, University of Marburg
- Host: Prof. Tobias Friedrich, HPI Managing Director and Head of “Algorithm Engineering”
Abstract
In 2002, Tim Peters invented Timsort, a clever Mergesort variant, for the CPython reference implementation of the Python programming language. Timsort is both effective in Python and a popular export product: it is used in many languages and frameworks, notably Open-JDK, the Android runtime, and the V8 JavaScript engine. Despite its widespread use, algorithms researchers eventually discovered two flaws in Tim-sort's underlying algorithm: The first could lead to a stack overflow in CPython and Java; although meanwhile fixed, it exposed conceptual intricacies of the algorithm. The second flaw concerns its performance: the order in which detected sorted segments, the “runs” of the input, are merged, can be 50% more costly than necessary. Based on ideas from optimal alphabetic trees, our Powersort merge policy finds nearly opti-mal merging orders with negligible overhead and using a much more transparent rule. Since Python 3.11, it is part of the CPython reference implementation. The talk will describe the involved algorithms assuming no prior familiarity.
About Prof. Sebastian Wild
Sebastian Wild leads the Algorithms Group in the Department of Computer Science at Uni-versity of Marburg and is a Senior Lecturer at the University of Liverpool. His research in-terests include space-efficient data structures, analysis of algorithms, and engineering of foundational algorithms. Before joining Marburg, he was a Lecturer at University of Liver-pool and, before that, Postdoctoral Fellow at the University of Waterloo. His PhD on the analysis of multiway quicksort, obtained from the University of Kaiserslautern, received the GI Dissertationspreis 2016. More info