[RFC] Proposal adding new sorting algorithm, bsort() to libc

From: Hans Petter Selasky <hps_at_selasky.org>
Date: Thu, 08 Sep 2022 10:50:28 UTC
See:
https://reviews.freebsd.org/D36493

Looking through base I see qsort() being used in places it shouldn't be 
used. For example in fts_open().

If for example you fill a directory with 64k simply numerical file names 
in the wrong order and ask fts_open() to sort these ascending for 
example, qsort() will end stuck for a long-long time. So either switch 
to mergesort, or if malloc() is unacceptable, use something like bsort() 
which I've implemented in the above review as a drop-in replacement for 
qsort(). The advantage with bsort() is that in can be CPU accelerated, 
due to fixed comparison patterns.

Quick sort is not always a quick sorting algorithm. Quick means simple, 
and not clever this time.

For the qsort's bad pattern, sorting 4096 entries 1024 times in a row took:

qsort: 15 seconds
bsort: 230 milliseconds (non-CPU accelerated)
mergesort: 30 milliseconds

The problem with qsort() is that as the array size grows, the time 
consumption just gets worse and worse for the bad-patterns.

Sorry there is no nice and fancy paper yet about this.

--HPS