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
