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
