Vincent Jugé <vincent.j...@u-pem.fr> added the comment: 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 runstack.py 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. Best, Vincent ---------- Added file: https://bugs.python.org/file47839/runstack.py _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue34561> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
