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
Date 2018-09-04.18:46:31
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
"Galloping" is the heart & soul of Python's sorting algorithm.  It's explained in detail here:

The Java fork of the sorting code has had repeated bugs due to reducing the size of "the stack" used to hold merge states.  Read the papers already referenced for details about that.

There is no "bug" here in the Python version.  It's that the complex code Java keeps tripping over ;-) , _could_ (possibly) be replaced by simpler code where the max stack size needed is obvious; that (e.g.) 2-merge moves around less memory overall in some cases where the current scheme is particularly wasteful in this respect; and that Munro & Wild present more ambitious merge-ordering schemes that are said to be provably near-optimal in a broader sense than 2-merge achieves.
Date User Action Args
2018-09-04 18:46:31tim.peterssetrecipients: + tim.peters, koos.zevenhoven
2018-09-04 18:46:31tim.peterssetmessageid: <>
2018-09-04 18:46:31tim.peterslinkissue34561 messages
2018-09-04 18:46:31tim.peterscreate