qsort switching to insertsort

[Tristan Verniquet]

> From: owner-freebsd-hackers at freebsd.org <owner-freebsd-hackers at freebsd.org> on behalf of Mitchell <mitchell at wyatt672earp.force9.co.uk>
> Sent: Sunday, 27 November 2016 10:38 PM
> To: freebsd-hackers at 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