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.or=
g> 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
> =A0
>=A0
> In "Numerical Recipes" (Press, Teukolsky, Vetterling & Flannery) the=A0
> Partitioning Element chosen is the median of the First, Middle & Last. Th=
ey=A0
> 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 =3D (char *)a + (n / 2) * es;
if (n > 7) {
=A0 =A0 =A0 =A0pl =3D a;
=A0 =A0 =A0 =A0pn =3D (char *)a + (n - 1) * es;
=A0 =A0 =A0 =A0if (n > 40) {
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0d =3D (n / 8) * es;
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0pl =3D med3(pl, pl + d, pl + 2 * d, cmp, thu=
nk);
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0pm =3D med3(pm - d, pm, pm + d, cmp, thunk);
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0pn =3D med3(pn - 2 * d, pn - d, pn, cmp, thu=
nk);
=A0 =A0 =A0 =A0}
=A0 =A0 =A0 =A0pm =3D 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 =3D=3D 0) case with certain se=
ts of data.
Tristan
=
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?ME1PR01MB0546BE73D7A316ACB03448F4838B0>