diff options
| author | Benjamin Peterson <benjamin@python.org> | 2015-02-25 15:12:26 (GMT) |
|---|---|---|
| committer | Benjamin Peterson <benjamin@python.org> | 2015-02-25 15:12:26 (GMT) |
| commit | 082a960425d23062f577650390a2d74ac98dd07d (patch) | |
| tree | 753aab64ce703ae29a1f8261dce5873a0a0cb455 | |
| parent | ebcbbfb9a2e1ccb86f8793efa98dffaaa2c088e6 (diff) | |
| download | cpython-082a960425d23062f577650390a2d74ac98dd07d.zip cpython-082a960425d23062f577650390a2d74ac98dd07d.tar.gz cpython-082a960425d23062f577650390a2d74ac98dd07d.tar.bz2 | |
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"
| -rw-r--r-- | Objects/listobject.c | 3 |
1 files changed, 2 insertions, 1 deletions
diff --git a/Objects/listobject.c b/Objects/listobject.c index f753643..1f43ba2 100644 --- a/Objects/listobject.c +++ b/Objects/listobject.c @@ -1800,7 +1800,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) |