Author: Benjamin Peterson <[email protected]>
Branch:
Changeset: r76148:8ea07be32d98
Date: 2015-02-25 13:57 -0500
http://bitbucket.org/pypy/pypy/changeset/8ea07be32d98/
Log: fix merge_collapse to actually maintain the invariant it purports to
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"
Also https://bugs.python.org/issue23515
diff --git a/rpython/rlib/listsort.py b/rpython/rlib/listsort.py
--- a/rpython/rlib/listsort.py
+++ b/rpython/rlib/listsort.py
@@ -501,7 +501,8 @@
def merge_collapse(self):
p = self.pending
while len(p) > 1:
- if len(p) >= 3 and p[-3].len <= p[-2].len + p[-1].len:
+ if ((len(p) >= 3 and p[-3].len <= p[-2].len + p[-1].len) or
+ (len(p) >= 4 and p[-4].len <= p[-3].len + p[-2].len)):
if p[-3].len < p[-1].len:
self.merge_at(-3)
else:
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
