From b808d590a24066bc03d21b55ed5e890a012477a8 Mon Sep 17 00:00:00 2001 From: Benjamin Peterson Date: Wed, 25 Feb 2015 10:12:26 -0500 Subject: fix merge_collapse to actually maintain the invariant it purports to (closes #23515) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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" --- Objects/listobject.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/Objects/listobject.c b/Objects/listobject.c index fd5a72a..b6c1d78 100644 --- a/Objects/listobject.c +++ b/Objects/listobject.c @@ -1832,7 +1832,8 @@ merge_collapse(MergeState *ms) 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) -- cgit v0.12