Powersort in official Python 3.11 release
Our sorting method Powersort is used as default
list.sort() algorithm in CPython, the reference implementation of the
Python programming language.
Here’s the entry from the official Python changelog:
bpo-34561: List sorting now uses the merge-ordering strategy from Munro and Wild’s
powersort(). Unlike the former strategy, this is provably near-optimal in the entropy of the distribution of run lengths. Most uses of
list.sort()probably won’t see a significant time difference, but may see significant improvements in cases where the former strategy was exceptionally poor. However, as these are all fast linear-time approximations to a problem that’s inherently at best quadratic-time to solve truly optimally, it’s also possible to contrive cases where the former strategy did better.
The change had been included in the development version of CPython, but with the official release of Python 3.11, Powersort is now on route to be deployed to hundreds of millions of devices, on top of already being in active use in PyPy.
Powersort is explained in our original publication and (in my biased opinion in a much clearer way 😅) in the talk slides; I told the full and updated story also in my algorithms lecture (preceeded there with an intro to adaptive sorting).
Very recently, we showed how to extend Powersort to multiway merges, looking very promising in first experiments.
- ACM TechNews (2022-12-14)
- University of Liverpool News story (2022-12-12)
on LinkedIn post
- London Daily News