Tim Peters <t...@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 <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
