Re: qsort, once again

On 3/16/06, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> So we still have a problem of software archaeology: who added the
> insertion sort switch to the NetBSD version, and on what grounds?



AFAICS, the insertion sort was added in BSD 4.4-lite and was inherited by
NetBSD in CVS version 1.1.1.2.

The previous version in NetBSD (before 4.4-lite) also included an insertion
sort with the comment:

/*
 * Knuth, Vol. 3, page 116, Algorithm Q, step b, argues that a single pass
 * of straight insertion sort after partitioning is complete is better than
 * sorting each small partition as it is created.  This isn't correct in this
 * implementation because comparisons require at least one (and often two)
 * function calls and are likely to be the dominating expense of the sort.
 * Doing a final insertion sort does more comparisons than are necessary
 * because it compares the "edges" and medians of the partitions which are
 * known to be already sorted.
 *
 * This is also the reasoning behind selecting a small THRESH value (see
 * Knuth, page 122, equation 26), since the quicksort algorithm does less
 * comparisons than the insertion sort.
 */


--
Jonah H. Harris, Database Internals Architect
EnterpriseDB Corporation
732.331.1324