[issue34561] Replace list sorting merge_collapse()?

[Tim Peters]

Tim Peters <tim at python.org> added the comment:

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.

----------
Added file: https://bugs.python.org/file47779/runstack.py

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue34561>
_______________________________________