pqsort.c: remove the "switch to insertion sort" optimization.

It causes catastrophic performance for certain inputs.

Relevant NetBSD commit:

http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/stdlib/qsort.c?rev=1.20&content-type=text/x-cvsweb-markup&only_with_tag=MAIN

This fixes issue #968.

1 files changed, 1 insertions, 12 deletions

diff --git a/src/pqsort.c b/src/pqsort.c
index 9c57aacd0..57c217f94 100644
--- a/src/pqsort.c
+++ b/src/pqsort.c
@@ -102,10 +102,9 @@ _pqsort(void *a, size_t n, size_t es,
 {
 	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
 	size_t d, r;
-	int swaptype, swap_cnt, cmp_result;
+	int swaptype, cmp_result;
 
 loop:	SWAPINIT(a, es);
-	swap_cnt = 0;
 	if (n < 7) {
 		for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
 			for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
@@ -132,7 +131,6 @@ loop:	SWAPINIT(a, es);
 	for (;;) {
 		while (pb <= pc && (cmp_result = cmp(pb, a)) <= 0) {
 			if (cmp_result == 0) {
-				swap_cnt = 1;
 				swap(pa, pb);
 				pa += es;
 			}
@@ -140,7 +138,6 @@ loop:	SWAPINIT(a, es);
 		}
 		while (pb <= pc && (cmp_result = cmp(pc, a)) >= 0) {
 			if (cmp_result == 0) {
-				swap_cnt = 1;
 				swap(pc, pd);
 				pd -= es;
 			}
@@ -149,17 +146,9 @@ loop:	SWAPINIT(a, es);
 		if (pb > pc)
 			break;
 		swap(pb, pc);
-		swap_cnt = 1;
 		pb += es;
 		pc -= es;
 	}
-	if (swap_cnt == 0) {  /* Switch to insertion sort */
-		for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
-			for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; 
-			     pl -= es)
-				swap(pl, pl - es);
-		return;
-	}
 
 	pn = (char *) a + n * es;
 	r = min(pa - (char *) a, pb - pa);