Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm.

On 4/19/23 22:17, Jessica Clarke wrote:
> pdqsort is n log n time, in-place and doesn’t allocate, and is used,
> for example, for Rust’s standard sort_unstable.

Hi Jessica,

Like many many people have tried over the years, to improve the belated 
QuickSort (*) algorithm since it was invented, by catching bad behaviour 
and then fallback to other algorithms, pdqsort() is not a solution!

Yes, it is probably "N log N" time, but if you read the code carefully, 
it falls back to heapsort(), which indeed uses malloc(), which is 
exactly my point, that I want to avoid.

Please come forward with a "N log N" time algorithm which is malloc() 
and alloca() free, and then we'll talk!

And not at least BSD-2-clause licensed and not covered by any patents, 
GPLv2 or whatever!

--HPS

(*) https://en.wikipedia.org/wiki/Quicksort