diff options
author | Tim Peters <tim.peters@gmail.com> | 2002-07-19 06:12:32 (GMT) |
---|---|---|
committer | Tim Peters <tim.peters@gmail.com> | 2002-07-19 06:12:32 (GMT) |
commit | 0fe977c4a91f93a53e598af05c7d99f4e1a59913 (patch) | |
tree | 114faa4a6e356aa16711a41b93ce73905a7f91f2 /Objects/listobject.c | |
parent | 326b44871eb9dcf98e286208bf2b2799edf2ba9e (diff) | |
download | cpython-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.c | 15 |
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) |