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 koos.zevenhoven, tim.peters, xtreak
Date 2018-09-06.22:27:09
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1536272829.61.0.56676864532.issue34561@psf.upfronthosting.co.za>
In-reply-to
Content
No, there's no requirement that run lengths on the stack be ordered in any way by magnitude.  That's simply one rule timsort uses, as well as 2-merge and various other schemes discussed in papers.  powersort has no such rule, and that's fine.

Regardless, rules must be such that the max stack size is at worst logarithmic in the number of array elements.  It's also nice if it's obvious that a sequence of equal-length runs will lead to perfectly balanced merges, which is "obvious enough" with the timsort and 2-merge rules.  It also happens to be true of the powersort rules, but harder to see from staring at code because it's hard to compute "node powers" in one's head.
History
Date User Action Args
2018-09-06 22:27:09tim.peterssetrecipients: + tim.peters, koos.zevenhoven, xtreak
2018-09-06 22:27:09tim.peterssetmessageid: <1536272829.61.0.56676864532.issue34561@psf.upfronthosting.co.za>
2018-09-06 22:27:09tim.peterslinkissue34561 messages
2018-09-06 22:27:09tim.peterscreate