This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author vincent.juge
Recipients koos.zevenhoven, tim.peters, vincent.juge, xtreak
Date 2018-10-02.09:51:27
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
After having worked a little bit on improving AdaptiveShiversSort on few-run cases, I designed a new version of the algorithm, called shivers2 in the file joined to this message

It looks more complicated than the original AdaptiveShiversSort but the spirit, inspired by your comments, is as follows:
- we allow the second (bottom-most) element of the stack to be moderately larger than the bottom-most one; if that 2nd element were way larger than the 1st one, merging them, even if not optimal, would not be too painful anyways;
- we may force a merge between these 1st and 2nd elements only when the 2nd element is about to be merged with the 3rd one;
- similarly, we allow the top-most element of the stack to be moderately larger than the second top-most one;
- otherwise, we stick to the behaviour of AdaptiveShiversSort.

This variant's performance seems comparable with Powersort's.
Reasonable follow-up work that I plan to do in the coming weeks (when I have time to do so) is:
- prove that the new algorithm still runs in n H + O(n),
- investigate whether we can have guarantees such as "this new sort's merge cost is at most XXX times larger than the optimal merge cost",
- investigate improvements for Powersort.

Given its excellent overall performance, I think that trying to slightly tweak Powersort in cases it underperforms other sorts might be worth some effort.


Date User Action Args
2018-10-02 09:51:27vincent.jugesetrecipients: + vincent.juge, tim.peters, koos.zevenhoven, xtreak
2018-10-02 09:51:27vincent.jugesetmessageid: <>
2018-10-02 09:51:27vincent.jugelinkissue34561 messages
2018-10-02 09:51:27vincent.jugecreate