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 tim.peters
Recipients koos.zevenhoven, tim.peters, vincent.juge, xtreak
Date 2021-08-29.02:59:33
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
The merge order was mentioned on python-dev today, and a quick web searched turned up a revision of Vincent Jugé's "Adaptive Shivers Sort: An Alternative Sorting Algorithm" paper I hadn't seen before:

Its "length-adaptive ShiversSort" variation sure _sounds_ like it was intended to address the issues we discussed here (some "bad" cases when very few runs are in play).

The analyses in that paper show that length-adaptive ShiversSort, and powersort, have the same asymptotic best and worst-case behaviors. Average case? Who knows? Hard to believe it could really be an issue, because even the worst cases are pretty darn good.

So length-adaptive ShiversSort is worth looking into. But, if someone has the energy to pursue it, I'd be happy, at this point, just to give plain old "adaptive ShiversSort" a try. The version of the paper linked to above even lists the precise changes needed to CPython's code to implement it (although a code review would ask for changes, most obviously that its "int x" is too narrow an integer type).
Date User Action Args
2021-08-29 02:59:33tim.peterssetrecipients: + tim.peters, koos.zevenhoven, xtreak, vincent.juge
2021-08-29 02:59:33tim.peterssetmessageid: <>
2021-08-29 02:59:33tim.peterslinkissue34561 messages
2021-08-29 02:59:33tim.peterscreate