Date: Sun, 27 Nov 2016 12:59:17 +0000 From: Tristan Verniquet <tris_vern@hotmail.com> To: Mitchell <mitchell@wyatt672earp.force9.co.uk>, "freebsd-hackers@freebsd.org" <freebsd-hackers@freebsd.org> Subject: Re: qsort switching to insertsort Message-ID: <ME1PR01MB0546BE73D7A316ACB03448F4838B0@ME1PR01MB0546.ausprd01.prod.outlook.com> In-Reply-To: <2066156.rDbTD5n9LR@daa860> References: <ME1PR01MB0546A92343D712D8439B299C83880@ME1PR01MB0546.ausprd01.prod.outlook.com> <CAOgwaMtsP159jgT4Faxg2jED1sh3N-zHKZRSqQNE0Cfh1NM1eA@mail.gmail.com> <ME1PR01MB054602129230B98C6127F607838B0@ME1PR01MB0546.ausprd01.prod.outlook.com>, <2066156.rDbTD5n9LR@daa860>
next in thread | previous in thread | raw e-mail | index | archive | help
> From: owner-freebsd-hackers@freebsd.org <owner-freebsd-hackers@freebsd.org> on behalf of Mitchell <mitchell@wyatt672earp.force9.co.uk>
> Sent: Sunday, 27 November 2016 10:38 PM
> To: freebsd-hackers@freebsd.org
> Subject: Re: qsort switching to insertsort
>
>
> In "Numerical Recipes" (Press, Teukolsky, Vetterling & Flannery) the
> Partitioning Element chosen is the median of the First, Middle & Last. They
> mention other techniques too.
The method used in FreeBSD qsort is the ninther approach. Ie the med3 of 3 med3's from the start, middle and end of the partition.
pm = (char *)a + (n / 2) * es;
if (n > 7) {
pl = a;
pn = (char *)a + (n - 1) * es;
if (n > 40) {
d = (n / 8) * es;
pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
pm = med3(pm - d, pm, pm + d, cmp, thunk);
pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
}
pm = med3(pl, pm, pn, cmp, thunk);
}
swap(a, pm);
https://en.wikipedia.org/wiki/Median#Ninther
So it is very hard to hit a bad pivot case with everyday data, but not that unrealistic to hit the insertsort (swap_cnt == 0) case with certain sets of data.
Tristan
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?ME1PR01MB0546BE73D7A316ACB03448F4838B0>