[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 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..