Date: Mon, 23 Aug 1999 00:28:32 -0700 (PDT) From: Christopher Seiwald <seiwald@perforce.com> To: a-wada@mars.dti.ne.jp, archie@whistle.com Cc: freebsd-hackers@FreeBSD.ORG Subject: Re: anybody love qsort.c? Message-ID: <199908230728.AAA24061@perforce.com> In-Reply-To: <199908220056.AA00050@a.mars.dti.ne.jp>
next in thread | previous in thread | raw e-mail | index | archive | help
Archie's mod to qsort:
| >- if (swap_cnt == 0) { /* Switch to insertion sort */
| >+ if (n <= 32 && swap_cnt == 0) { /* Switch to insertion sort */
As Akira Wada points out, this eliminates the benefit of the optimization
in the first place, which is to let isort take over if the data is largely
sorted in the first place.
Akira Wada's alternative mod:
| + pl = (char *)a; pn = (char *)a + (n - 1) * es;
| + while (pl < pn && cmp(pl, pl + es) <= 0) pl += es;
| + if (pl >= pn) return;
This is a little more comprehensive, but does throw in an extra pass
of comparisons, which (I'm sure) someone would complain about.
The alteration that I've tried and tested is to have the isort bail
back to qsort if it does more than N swaps. I put N at 1024, which
worked for my data :). This is almost guaranteed to do no more work
than the current logic, because it it only gives up on the isort when
it has evidence that the isort is doing too much work.
Christopher
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-hackers" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199908230728.AAA24061>