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
