More sort cleanup: Moved the special cases from samplesortslice into
listsort. If the former calls itself recursively, they're a waste of
time, since it's called on a random permutation of a random subset of
elements. OTOH, for exactly the same reason, they're an immeasurably
small waste of time (the odds of finding exploitable order in a random
permutation are ~= 0, so the special-case loops looking for order give
up quickly). The point is more for conceptual clarity.
Also changed some "assert comments" into real asserts; when this code
was first written, Python.h didn't supply assert.h.
diff --git a/Objects/listobject.c b/Objects/listobject.c
index bc79cd1..7d3d48f 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -1005,43 +1005,10 @@
int n, extra, top, extraOnRight;
struct SamplesortStackNode stack[STACKSIZE];
- /* assert lo <= hi */
+ assert(lo <= hi);
n = hi - lo;
-
- /* ----------------------------------------------------------
- * Special cases
- * --------------------------------------------------------*/
- if (n < 2)
- return 0;
-
- /* Set r to the largest value such that [lo,r) is sorted.
- This catches the already-sorted case, the all-the-same
- case, and the appended-a-few-elements-to-a-sorted-list case.
- If the array is unsorted, we're very likely to get out of
- the loop fast, so the test is cheap if it doesn't pay off.
- */
- /* assert lo < hi */
- for (r = lo+1; r < hi; ++r) {
- IFLT(*r, *(r-1))
- break;
- }
- /* [lo,r) is sorted, [r,hi) unknown. Get out cheap if there are
- few unknowns, or few elements in total. */
- if (hi - r <= MAXMERGE || n < MINSIZE)
- return binarysort(lo, hi, r, compare);
-
- /* Check for the array already being reverse-sorted. Typical
- benchmark-driven silliness <wink>. */
- /* assert lo < hi */
- for (r = lo+1; r < hi; ++r) {
- IFLT(*(r-1), *r)
- break;
- }
- if (hi - r <= MAXMERGE) {
- /* Reverse the reversed prefix, then insert the tail */
- reverse_slice(lo, r);
- return binarysort(lo, hi, r, compare);
- }
+ if (n < MINSIZE)
+ return binarysort(lo, hi, lo, compare);
/* ----------------------------------------------------------
* Normal case setup: a large array without obvious pattern.
@@ -1093,7 +1060,7 @@
* Partition [lo, hi), and repeat until out of work.
* --------------------------------------------------------*/
for (;;) {
- /* assert lo <= hi, so n >= 0 */
+ assert(lo <= hi);
n = hi - lo;
/* We may not want, or may not be able, to partition:
@@ -1103,8 +1070,8 @@
*/
if (n < MINPARTITIONSIZE || extra == 0) {
if (n >= MINSIZE) {
- /* assert extra == 0
- This is rare, since the average size
+ assert(extra == 0);
+ /* This is rare, since the average size
of a final block is only about
ln(original n). */
if (samplesortslice(lo, hi, compare) < 0)
@@ -1184,7 +1151,7 @@
duplicates later. */
l = lo + 1;
r = hi - 1;
- /* assert lo < l < r < hi (small n weeded out above) */
+ assert(lo < l && l < r && r < hi);
do {
/* slide l right, looking for key >= pivot */
@@ -1208,9 +1175,8 @@
} while (l < r);
- /* assert lo < r <= l < hi
- assert r == l or r+1 == l
- everything to the left of l is < pivot, and
+ assert(lo < r && r <= l && l < hi);
+ /* everything to the left of l is < pivot, and
everything to the right of r is >= pivot */
if (l == r) {
@@ -1219,13 +1185,12 @@
else
--r;
}
- /* assert lo <= r and r+1 == l and l <= hi
- assert r == lo or a[r] < pivot
- assert a[lo] is pivot
- assert l == hi or a[l] >= pivot
- Swap the pivot into "the middle", so we can henceforth
- ignore it.
- */
+ assert(lo <= r && r+1 == l && l <= hi);
+ /* assert r == lo or a[r] < pivot */
+ assert(*lo == pivot);
+ /* assert l == hi or a[l] >= pivot */
+ /* Swap the pivot into "the middle", so we can henceforth
+ ignore it. */
*lo = *r;
*r = pivot;
@@ -1250,13 +1215,12 @@
++l;
}
- /* assert lo <= r < l <= hi
- Partitions are [lo, r) and [l, hi) */
-
- /* push fattest first; remember we still have extra PPs
+ assert(lo <= r && r < l && l <= hi);
+ /* Partitions are [lo, r) and [l, hi)
+ :ush fattest first; remember we still have extra PPs
to the left of the left chunk and to the right of
the right chunk! */
- /* assert top < STACKSIZE */
+ assert(top < STACKSIZE);
if (r - lo <= hi - l) {
/* second is bigger */
stack[top].lo = l;
@@ -1283,33 +1247,77 @@
return -1;
}
-#undef IFLT
-
static PyTypeObject immutable_list_type;
static PyObject *
listsort(PyListObject *self, PyObject *args)
{
- int err;
+ int k;
PyObject *compare = NULL;
+ PyObject **hi, **p;
PyTypeObject *savetype;
if (args != NULL) {
if (!PyArg_ParseTuple(args, "|O:sort", &compare))
return NULL;
}
+
savetype = self->ob_type;
+ if (self->ob_size < 2) {
+ k = 0;
+ goto done;
+ }
+
self->ob_type = &immutable_list_type;
- err = samplesortslice(self->ob_item,
- self->ob_item + self->ob_size,
- compare);
- self->ob_type = savetype;
- if (err < 0)
+ hi = self->ob_item + self->ob_size;
+
+ /* Set p to the largest value such that [lo, p) is sorted.
+ This catches the already-sorted case, the all-the-same
+ case, and the appended-a-few-elements-to-a-sorted-list case.
+ If the array is unsorted, we're very likely to get out of
+ the loop fast, so the test is cheap if it doesn't pay off.
+ */
+ for (p = self->ob_item + 1; p < hi; ++p) {
+ IFLT(*p, *(p-1))
+ break;
+ }
+ /* [lo, p) is sorted, [p, hi) unknown. Get out cheap if there are
+ few unknowns, or few elements in total. */
+ if (hi - p <= MAXMERGE || self->ob_size < MINSIZE) {
+ k = binarysort(self->ob_item, hi, p, compare);
+ goto done;
+ }
+
+ /* Check for the array already being reverse-sorted, or that with
+ a few elements tacked on to the end. */
+ for (p = self->ob_item + 1; p < hi; ++p) {
+ IFLT(*(p-1), *p)
+ break;
+ }
+ /* [lo, p) is reverse-sorted, [p, hi) unknown. */
+ if (hi - p <= MAXMERGE) {
+ /* Reverse the reversed prefix, then insert the tail */
+ reverse_slice(self->ob_item, p);
+ k = binarysort(self->ob_item, hi, p, compare);
+ goto done;
+ }
+
+ /* A large array without obvious pattern. */
+ k = samplesortslice(self->ob_item, hi, compare);
+
+done: /* The IFLT macro requires a label named "fail". */;
+fail:
+ self->ob_type = savetype;
+ if (k >= 0) {
+ Py_INCREF(Py_None);
+ return Py_None;
+ }
+ else
return NULL;
- Py_INCREF(Py_None);
- return Py_None;
}
+#undef IFLT
+
int
PyList_Sort(PyObject *v)
{