libc: Drop incorrect qsort optimization

As pointed out in the PR and the article linked below, the switch to
insertion sort in the BSD qsort code is based on a misunderstanding of
Knuth's TAOCP and

libc: Drop incorrect qsort optimization

As pointed out in the PR and the article linked below, the switch to
insertion sort in the BSD qsort code is based on a misunderstanding of
Knuth's TAOCP and is actually a pessimization. As demonstrated by the
added test, it is trivially easy to construct pathological input which
results in quadratic runtime. Without that misguided optimization, the
same input runs in nearly linearithmic time.

https://www.raygard.net/2022/02/26/Re-engineering-a-qsort-part-3

PR: 287089
MFC after: 1 week
Reviewed by: imp
Differential Revision: https://reviews.freebsd.org/D51907

show more ...