[issue34561] Replace list sorting merge_collapse()?
Vincent Jugé 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 <https://bugs.python.org/issue34561> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue34561] Replace list sorting merge_collapse()?
Vincent Jugé added the comment: I see... Indeed, my only goal when adapting Shivers Sort was to maintain some invariant that would make the analysis easy, while mimicking the arguments developed by Buss & Knop for their analysis of (plain) Shivers Sort. It is, however, sure that the n(H+4) upper bound I get should be refined when H is small, which more or less amounts to tackling the 3-run case you mention. I am reasonably convinced that the current version of Adaptive Shivers Sort could be adapted to take this problem into account, while keeping its overall simple stricture and complexity analysis. If this first step turns out to be feasible, I will also look at the latest version of runstack.py to investigate other possible improvements on Adaptive Shivers Sort. -- ___ Python tracker <https://bugs.python.org/issue34561> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue34561] Replace list sorting merge_collapse()?
Vincent Jugé added the comment: Dear all, After me and my colleagues worked on the first paper you mention, I recently created another merge-based sorting algorithm, which I called "Adaptive Shivers Sort". This is a close variant of the Augmented Shivers Sort presented by Buss & Knop in their article https://arxiv.org/abs/1801.04641 Like Munro & Wild's Powersort and Peeksort, this algorithm has an optimal worst-case running time (up to a linear additive constant) when measured with the merge cost model that is used in all the articles you cite in this discussion. It also maintains a stack of size log_2(n). I could not prove such an optimality result for Buss & Knop Augmented Shivers Sort. Custom tests that I had performed suggest that this algorithm is, in practice, as efficient as Munro & Wild's algorithms, and also does not suffer from critically bad cases. Moreover, like Buss & Knop's 2-merge, and unlike Munro & Wild's Powersort and Peeksort, this algorithm has the advantage of having a structure that is very similar to that of Timsort, which may be an advantage in your situation. That is why, upon reading your discussion, I refurbished my notes about Adaptive Shivers Sort, which you may find here: http://igm.univ-mlv.fr/~juge/papers/shivers_arxiv.pdf These notes include a description of the algorithm and a worst-time complexity analysis. If extending my analysis of this algorithm or investigating tuning details were of interest for you, I would be happy to help. Best regards, Vincent Jugé -- nosy: +vincent.juge ___ Python tracker <https://bugs.python.org/issue34561> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
