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-09-21.14:44:08
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
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

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:

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é
Date User Action Args
2018-09-21 14:44:08vincent.jugesetrecipients: + vincent.juge, tim.peters, koos.zevenhoven, xtreak
2018-09-21 14:44:08vincent.jugesetmessageid: <>
2018-09-21 14:44:08vincent.jugelinkissue34561 messages
2018-09-21 14:44:08vincent.jugecreate