[issue23515] Bad logic in timsort's merge_collapse

2015-02-25 Thread Tim Peters
Tim Peters added the comment: Thanks, Terry! Absolutely agreed: a logical error is an error, and will bite us eventually, regardless of whether it does so today. I'm very glad the researchers went to all the trouble to analyze this one :-) -- ___

[issue23515] Bad logic in timsort's merge_collapse

2015-02-25 Thread Terry J. Reedy
Terry J. Reedy added the comment: I sent a note to the lead author Stijn de Gouw and mentioned that the repository has moved from svn to hg.python.org. This change may be moot, but I think it worth our effort to keep our code as clean as possible and to encourage automated code checks, as we h

[issue23515] Bad logic in timsort's merge_collapse

2015-02-25 Thread Serhiy Storchaka
Serhiy Storchaka added the comment: Thank you for your explanation Tim. -- ___ Python tracker ___ ___ Python-bugs-list mailing list Un

[issue23515] Bad logic in timsort's merge_collapse

2015-02-25 Thread Tim Peters
Tim Peters added the comment: Since it's impossible to trigger the error on any current machine anyway (no machine has enough memory), increasing the size of the stack would be absurd. If you read the paper, they note that this is what the Java folks first did (they changed this part of timso

[issue23515] Bad logic in timsort's merge_collapse

2015-02-25 Thread Serhiy Storchaka
Serhiy Storchaka added the comment: How additional test affects performance? May be just increase MAX_MERGE_PENDING? -- nosy: +serhiy.storchaka ___ Python tracker ___ ___

[issue23515] Bad logic in timsort's merge_collapse

2015-02-25 Thread Tim Peters
Tim Peters added the comment: @Benjamin, bless you for changing their "n-1 > 0" to "n > 1", and for adding parentheses to make the intended grouping obvious instead of a puzzle, and for swapping the addends on the RHS of the new test. Thank you - perfect :-) -- __

[issue23515] Bad logic in timsort's merge_collapse

2015-02-25 Thread Roundup Robot
Roundup Robot added the comment: New changeset 325aec842e3e by Benjamin Peterson in branch '2.7': fix merge_collapse to actually maintain the invariant it purports to (closes #23515) https://hg.python.org/cpython/rev/325aec842e3e New changeset 620cb13008b7 by Benjamin Peterson in branch '3.4':

[issue23515] Bad logic in timsort's merge_collapse

2015-02-24 Thread Chris Kaynor
Changes by Chris Kaynor : -- nosy: +DragonFireCK ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.p

[issue23515] Bad logic in timsort's merge_collapse

2015-02-24 Thread Alex Gaynor
Changes by Alex Gaynor : -- nosy: +alex ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org

[issue23515] Bad logic in timsort's merge_collapse

2015-02-24 Thread Tim Peters
New submission from Tim Peters: Some researchers found an error in the logic of merge_collapse, explained here, and with corrected code shown in section 3.2: http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ This affects all current versi