[issue34561] Replace list sorting merge_collapse()?

[Tim Peters]

Tim Peters <tim at python.org> added the comment:

I created a PR that implements the powersort merge strategy:

https://github.com/python/cpython/pull/28108

Across all the time this issue report has been open, that strategy continues to be the top contender. Enough already ;-) It's indeed a more difficult change to make to the code, but that's in relative terms. In absolute terms, it's not at all a hard change.

Laurent, if you find that some variant of ShiversSort actually runs faster than that, let us know here! I'm a big fan of Vincent's innovations too, but powersort seems to do somewhat better "on average" than even his length-adaptive ShiversSort (and implementing that too would require changing code outside of merge_collapse()).

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue34561>
_______________________________________