Archie Cobbs wrote...
>Christopher Seiwald writes:
>> But as I'm proposing a change to a fairly sensitive piece of code, I'd
>> like to keep the change as modest as possible.
>
>How about this?
>
>Index: qsort.c
>===================================================================
>RCS file: /home/ncvs/src/lib/libc/stdlib/qsort.c,v
>retrieving revision 1.7
>diff -u -r1.7 qsort.c
>--- qsort.c 1997/02/22 15:03:14 1.7
>+++ qsort.c 1999/08/21 01:35:35
>@@ -153,7 +153,7 @@
> pb += es;
> pc -= es;
> }
>- if (swap_cnt == 0) { /* Switch to insertion sort */
>+ if (n <= 32 && 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)
>
>
>-Archie
I think your modification would avoid the degeneration indicated
by Christopher Seiwald, but degrade the advantage for the dataset
sorted completely or sorted in reversed order, down to nearly
equal for random dataset.
I added a routine before selecting pivot to test current partition
sorted already and if so, to bypass partitioning. It works well
for dataset sorted in order, but doesn't work for dataset in
reversed order. I believe a reversed dataset would be partitioned
into two subpartitions sorted in order at the 1'st pass of
the partitionigs. Is this incorrect ?
--------------------------------------------------------------
for qsort.c,v 1.9 1998/06/30 11:05:11
@@ -102,2 +102,5 @@
swap_cnt = 0;
+ pl = (char *)a; pn = (char *)a + (n - 1) * es;
+ while (pl < pn && cmp(pl, pl + es) pl += es;
+ if (pl >= pn) return;
if (n < 7) {
--------------------------------------------------------------
-Akira Wada
To Unsubscribe: send mail to majord...@freebsd.org
with "unsubscribe freebsd-hackers" in the body of the message
