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 tim.peters
Date 2018-09-01.21:37:41
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1535837861.83.0.56676864532.issue34561@psf.upfronthosting.co.za>
In-reply-to
Content
The attached runstack.py models the relevant parts of timsort's current merge_collapse and the proposed 2-merge.  Barring conceptual or coding errors, they appear to behave much the same with respect to "total cost", with no clear overall winner.  Of course cases can be constructed to make either look better.  As expected, twomerge requires fewer stack levels.  And they behave identically when all runs have the same length.

Note that the notion of "cost" here is simply that merging runs of lengths A and B always has cost A+B.  That should be viewed as worst case, where the rest of timsort finds nothing to exploit.
History
Date User Action Args
2018-09-01 21:37:41tim.peterssetrecipients: + tim.peters
2018-09-01 21:37:41tim.peterssetmessageid: <1535837861.83.0.56676864532.issue34561@psf.upfronthosting.co.za>
2018-09-01 21:37:41tim.peterslinkissue34561 messages
2018-09-01 21:37:41tim.peterscreate