[Laurent Lyaudet <email@example.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()?
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 python-dev mailing list.
(If it does then the search here:
Alas, that's been inactive for nearly 3 years, but we _were_ making
some decent progress before everyone got distracted by "more
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
I will try to provide a patch before the end of the week.
But first I will read
I took 5 minutes to fork and do a PR on my fork with the code for merge collapse :
As soon as I have something more polished I'll do a PR on python repo.
Any early feedback is welcome :)