Author: Benjamin Peterson <[email protected]>
Branch:
Changeset: r76151:11928c1ed7d0
Date: 2015-02-25 16:43 -0500
http://bitbucket.org/pypy/pypy/changeset/11928c1ed7d0/
Log: revert 8ea07be32d98; note merge_collapse actually does not
necessarily restore all invariants
diff --git a/rpython/rlib/listsort.py b/rpython/rlib/listsort.py
--- a/rpython/rlib/listsort.py
+++ b/rpython/rlib/listsort.py
@@ -496,13 +496,18 @@
# 1. len[-3] > len[-2] + len[-1]
# 2. len[-2] > len[-1]
#
+ # Note these invariants will not hold for the entire pending array even
+ # after this function completes. [1] This does not affect the
+ # correctness of the overall algorithm.
+ #
+ # [1]
http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
+ #
# See listsort.txt for more info.
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) or
- (len(p) >= 4 and p[-4].len <= p[-3].len + p[-2].len)):
+ if len(p) >= 3 and p[-3].len <= p[-2].len + p[-1].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
