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 LLyaudet, erlendaasland, koos.zevenhoven, tim.peters, vincent.juge, xtreak
Date 2021-08-29.23:42:55
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1630280575.96.0.101290038424.issue34561@roundup.psfhosted.org>
In-reply-to
Content
Added new runstack.py.

New `shivers2()` adds the implementation of adaptive ShiversSort from Vincent's later paper. While the code is simpler, it appears to behave identically.

New `shivers3()` adds, from the same paper, the new "length-adaptive ShiversSort". Wow! This is the only thing we've seen yet that's in the same universe as powersort. In fact, it usually does a tiny bit better (on the randomized cases). But it's not obvious how to rework its "if" test to be truly efficient (as-is, it needs two divisions, two calls to `log2()`, and two calls to `floor()`).

Worth some thought, though. From the results here, length-adaptive ShiversSort is a bigger improvement over (plain-old) adaptive ShiversSort than the latter is over timsort.
History
Date User Action Args
2021-08-29 23:42:56tim.peterssetrecipients: + tim.peters, koos.zevenhoven, xtreak, vincent.juge, erlendaasland, LLyaudet
2021-08-29 23:42:55tim.peterssetmessageid: <1630280575.96.0.101290038424.issue34561@roundup.psfhosted.org>
2021-08-29 23:42:55tim.peterslinkissue34561 messages
2021-08-29 23:42:55tim.peterscreate