[Python-checkins] cpython (2.7): fix merge_collapse to actually maintain the invariant it purports to (closes

[benjamin.peterson]

https://hg.python.org/cpython/rev/325aec842e3e
changeset:   94744:325aec842e3e
branch:      2.7
parent:      94737:8969c7f44d9e
user:        Benjamin Peterson <benjamin at python.org>
date:        Wed Feb 25 10:12:26 2015 -0500
summary:
  fix merge_collapse to actually maintain the invariant it purports to (closes #23515)

See
de Gouw, Stijn and Rot, Jurriaan and de Boer, Frank S and Bubel, Richard and Hähnle, Reiner
"OpenJDK’s java.utils.Collection.sort() is broken: The good, the bad and the worst case"

files:
  Objects/listobject.c |  3 ++-
  1 files changed, 2 insertions(+), 1 deletions(-)


diff --git a/Objects/listobject.c b/Objects/listobject.c
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -1800,7 +1800,8 @@
     assert(ms);
     while (ms->n > 1) {
         Py_ssize_t n = ms->n - 2;
-        if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len) {
+        if ((n > 0 && p[n-1].len <= p[n].len + p[n+1].len) ||
+            (n > 1 && p[n-2].len <= p[n-1].len + p[n].len)) {
             if (p[n-1].len < p[n+1].len)
                 --n;
             if (merge_at(ms, n) < 0)

-- 
Repository URL: https://hg.python.org/cpython