Talk:Powersort

Did Powersort really replaced Timsort?

In the article, it' stated Powersort replaced Timsort in CPython and PyPy. It's also stated that:

The implementation of Powersort in CPython began with version 3.11, replacing the older Timsort algorithm.

This is a bold claim, not supported by any official docs.

In the current (3.14) official Python docs, it's stated:

The Timsort algorithm used in Python does multiple sorts efficiently because it can take advantage of any ordering already present in a dataset.

https://docs.python.org/3.14/howto/sorting.html

In no official Python docs it's stated Python uses Powersort now.

The article quotes the CPython issue. In the final commit it's stated:

Switch to Munro & Wild "powersort" merge strategy. For list.sort(), replace our ad hoc merge ordering strategy with the principled, elegant, and provably near-optimal one from Munro and Wild's "powersort".'

Notice "merge strategy".

Also in the quoted PyPy commit, the commit comment is:

switch to "powersort" merging strategy by Munro and Wild in the timsort algorithm.

Notice the "merging strategy" and "in the timsort algorithm".

Furthermore it's worth noting that the author of the issue and the commit that adopted the powersort merge strategy in CPython, that taken 3 years of deep analysis, is tim-one, that is the nickname of Tim Peters. Pypy used the commit of Tim Peters to adapt its code.

It's uplifting reading this considerations of Tim Peters in the issue itself:

On randomly ordered input, timsort already strongly tends toward perfectly balanced merges, and there's no significant improvement to be had over that. On the other hand, on inputs with significant order that _can_ be exploited by this approach, the gains are far more due to "galloping" than to the order in which runs are merged. All these papers ignore galloping entirely.

It means that galloping is the main strategy that really make timsort effective, over merges.

Finally, the most sounding evidence is the final commit itself:

https://github.com/python/cpython/commit/5cb4c672d855033592f0e05162f887def236c00a#diff-6d09fc0f0b57214c2e3a838d366425836c296fa931fe9dc430f604b7e3950c29L318-R421

Only ~50 lines of non-comment code was added or changed, over 974 lines of timsort. Only a bit higher than 5%, It's really hard to argue that powersort replaced timsort.

Shortly, Python still uses Timsort. Tim Peters only changed the merge strategy with the powersort one, and the speed gain is really overestimated. Saying that Python uses powersort now because timsort adopted its merge strategy it's like saying Java was replaced by Python because it adopted task groups. Lucas Malor (talk) 00:32, 13 December 2025 (UTC)