From Quicksort to Timsort to Powersort: Unveiling the Evolution of CPython's Sorting Algorithm
hemi s.k (~hemi) |
Description:
Crafting a sorting function might seem straightforward, but developing a fast and dependable reference implementation is a challenge. This talk delves into the evolution of CPython's list sort function, revealing the journey behind its latest updates. After employing Quicksort for an extended period, Tim Peters devised Timsort, a clever variant of Mergesort, tailored for the CPython implementation. Timsort not only revolutionized sorting in Python but also became a widely adopted solution, powering languages and frameworks such as OpenJDK, Android runtime, and V8 JavaScript engine. Despite its success, researchers uncovered two flaws in Timsort's algorithm. The first, potentially leading to stack overflow in CPython and Java, remained undetected for a decade before being addressed. The second flaw, impacting performance, involved the merging order of sorted segments ("runs") in the input, resulting in unnecessary overhead. Drawing inspiration from the obscure puzzle of optimal alphabetic trees, the Powersort merge policy was devised, offering nearly optimal merging orders with minimal overhead. This enhancement has been integrated into the CPython implementation as of Python 3.11.0.
Target audience: Enthusiastic geeks who appreciate the power of algorithmic reasoning, programmers intrigued by optimising performance-critical code, and Python aficionados eager to uncover the secrets behind Python's efficient sorting algorithms.
Prerequisites:
- Basic understanding of sorting algorithms
- Familiarity with Python programming
- Interest in algorithmic optimization
- Curiosity about CPython's evolution
- Appreciation for historical context
Speaker Info:
Hello, I'm Hemangi Karchalkar. Armed with six years of professional programming experience and an enduring love for coding, I presently serve as a Senior Software Developer at EPAM Systems. Beyond my coding prowess, I find fulfillment in sharing knowledge with others. My passion lies in aiding individuals in their journey to success in the realms of data science and artificial intelligence. I've been fortunate to present at esteemed gatherings such as PyCon Italia 2023, Pycon India 2023, Pyconf Hyderabad 2022, Pycon Italia 2024, and GIDS Bangalore 2023.