summaryrefslogtreecommitdiffstats
path: root/Objects/listobject.c
diff options
context:
space:
mode:
authorTim Peters <tim.peters@gmail.com>2002-07-19 06:12:32 (GMT)
committerTim Peters <tim.peters@gmail.com>2002-07-19 06:12:32 (GMT)
commit0fe977c4a91f93a53e598af05c7d99f4e1a59913 (patch)
tree114faa4a6e356aa16711a41b93ce73905a7f91f2 /Objects/listobject.c
parent326b44871eb9dcf98e286208bf2b2799edf2ba9e (diff)
downloadcpython-0fe977c4a91f93a53e598af05c7d99f4e1a59913.zip
cpython-0fe977c4a91f93a53e598af05c7d99f4e1a59913.tar.gz
cpython-0fe977c4a91f93a53e598af05c7d99f4e1a59913.tar.bz2
binarysort() cleanup: Documented the key invariants, explained why they
imply this is a stable sort, and added some asserts.
Diffstat (limited to 'Objects/listobject.c')
-rw-r--r--Objects/listobject.c15
1 files changed, 13 insertions, 2 deletions
diff --git a/Objects/listobject.c b/Objects/listobject.c
index ce0f22e..bc79cd1 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -871,14 +871,25 @@ binarysort(PyObject **lo, PyObject **hi, PyObject **start, PyObject *compare)
l = lo;
r = start;
pivot = *r;
+ /* Invariants:
+ * pivot >= all in [lo, l).
+ * pivot < all in [r, start).
+ * The second is vacuously true at the start.
+ */
+ assert(l < r);
do {
p = l + ((r - l) >> 1);
IFLT(pivot, *p)
r = p;
else
- l = p + 1;
+ l = p+1;
} while (l < r);
- /* Pivot should go at l -- slide over to make room.
+ assert(l == r);
+ /* The invariants still hold, so pivot >= all in [lo, l) and
+ pivot < all in [l, start), so pivot belongs at l. Note
+ that if there are elements equal to pivot, l points to the
+ first slot after them -- that's why this sort is stable.
+ Slide over to make room.
Caution: using memmove is much slower under MSVC 5;
we're not usually moving many slots. */
for (p = start; p > l; --p)