I agree that a factor of 2, or even 1.03, would be worthwhile. But the biggest problem facing standard library authors is not frequently performing 1.5× or 2× worse than optimal; it's occasionally performing 10000× worse than optimal, like the story Bentley & McIlroy start out with in that paper about the organ-pipe array. (And that's why the Golang stdlib uses introsort.)

BTW, just because someone was optimizing their library parameters on a machine from 01987 (like the Sun-4/260) doesn't necessarily mean they were doing it before 01993. In 01993 I was using a VAX-11/785 from 01984. Hardware lasted longer in those days (it was less common to drop your SPARC on the sidewalk and spiderweb the touchscreen) and its higher cost forced it into longer service. https://books.google.com.ar/books?id=JRgDwCkMX_cC&pg=PP121&l... says the VAX-11/785's list price in 01984 was US$200k, equivalent to US$513k in 02021 according to the BLS CPI. Not counting the terminals and printers! (About 2000 kids learned to program on that beast, so it was probably a good expenditure for the school district.) In 01988 Sun listed the Sun-4/260 at a base price of US$40k (http://www.bitsavers.org/pdf/sun/Sun_Price_List_Dec88.pdf) but probably more realistically US$80k if you wanted a disk and some way to back it up. US$80k in 01988 is US$180k in 02021. So you might find yourself running a big machine long after it was obsolete.

But surely that sort of penny-pinching was unique to high schools like mine, not serious professionals like those writing FreeBSD's libc, GNU libc, and Bentley's SP&E article, written from the lofty sanctuary of Bell Labs? Well, Bentley's 01993 paper reports benchmark results (from 01992) on a MIPS R3000 (introduced 01988) and a VAX 8550 (introduced 01986).

Why didn't he benchmark it on any machine from that decade? Probably he didn't have one. And the glibc folks were mostly volunteers at that point. CSRG was still DoD-funded, but they disbanded in 01995 after 4.4. (I think a bunch of them were at BSDI for a while.)

— ⁂ —

The FreeBSD code is doing an insertion sort. Insertion sort looks a lot like bubble sort, and it took me a long time to appreciate the difference. One difference that's sometimes relevant for this sort of thing is that, on nearly-sorted data, insertion sort is O(N) and bubble sort is O(N²). But in this case that's not relevant because it's not running a single insertion-sort pass over the whole array after nearly-sorting it via quicksort; it's insertion-sorting each tiny partition. (The sorted part of the partition is the range from a up to pm.)

After N iterations of the outer loop of either insertion sort or bubble sort, one end of your array has N sorted items in it. (The bottom of the partition from a to a+n, in this case.) The difference is that insertion sort grows that sorted region by inserting the nearest unsorted element into it, while bubble sort grows it by inserting the smallest unsorted element into it (or largest, if you're sorting toward the top). So bubble sort only makes as much progress per pass as insertion sort, but it does a bunch of unnecessary extra work to do it (basically, the same work selection sort does); when sorting M randomly ordered items, insertion sort does on average ¼M† comparisons and swaps on each of the M passes, while bubble sort does ½M comparisons (and still ¼M swaps).

Never use bubble sort.

______

† Actually the number is something like ¼√(M² - M), I think. I'd have to go calculate it to be exact.