Re: qsort, once again

On 3/16/06, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)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