[Laurent Lyaudet <laurent.lyaudet@gmail.com>]
... My benchmarks could be improved but however I found that Shivers' sort and adaptive Shivers' sort (aka Jugé's sort) performs better than Tim's sort.
Cool! Could you move this to the issue report already open on this?
Replace list sorting merge_collapse()? https://bugs.python.org/issue34561
Thanks for the fast and kind answer :) I just did. Sorry for not checking the bugs reports before posting. I only checked that Shivers and Jugé did not appear in the archive of the
Hello, Le sam. 28 août 2021 à 19:38, Tim Peters <tim.peters@gmail.com> a écrit : python-dev mailing list. (If it does then the search here: https://mail.python.org/archives/list/python-dev@python.org/ is broken.)
Alas, that's been inactive for nearly 3 years, but we _were_ making some decent progress before everyone got distracted by "more important" stuff.
You'll see there that Vincent Jugé contributed another version, designed to address that his sort did substantially worse than what we already have in some cases with very few runs. Which, for reasons explained there, is likely important.
Before that, the best alternative known was - and by far - Munro & Wild's "powersort" merge strategy. That's deeply rooted in theory about fast approximations to optimal binary search trees.
Where that left off, Vincent was going to try proving properties of his new variant, plus investigate other ideas. Alas, that's where it ended, as Vincent ran out of time too.
In any case, yes, I'm entirely in favor of replacing timsort's merge strategy, by something with provably good properties even in worst cases. As explained in the issue report, the merge strategy I made up was merely the first thing I tried that didn't obviously suck ;-) - almost all the work went into making merging itself as zippy as reasonably possible..
I will try to provide a patch before the end of the week. But first I will read https://www.python.org/psf/contrib/ https://devguide.python.org/ I took 5 minutes to fork and do a PR on my fork with the code for merge collapse : https://github.com/LLyaudet/cpython/pull/1 As soon as I have something more polished I'll do a PR on python repo. Any early feedback is welcome :) Best regards, Laurent