[Laurent Lyaudet <laurent.lyau...@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..
_______________________________________________
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-le...@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at
https://mail.python.org/archives/list/python-dev@python.org/message/CQ32BVLF66ITQ6NBSYCQUPB7TPAGD5AF/
Code of Conduct: http://python.org/psf/codeofconduct/
