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

On 4/20/23 00:31, Jessica Clarke wrote:
> On 19 Apr 2023, at 22:41, Hans Petter Selasky <hselasky@freebsd.org> wrote:
>>
>> 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.
> 

Hi,

> Citation needed. This directly contradicts Rust’s documentation:

Sure, look at line 448 in there:

https://github.com/orlp/pdqsort/blob/master/pdqsort.h#L448

>> This sort is unstable (i.e., may reorder equal elements), in-place (i.e., does not allocate), and O(n * log(n)) worst-case.

Unfortunately it can end up allocating memory.

>>
>> Current implementation
>> The current algorithm is based on pattern-defeating quicksort by Orson Peters, which combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on slices with certain patterns. It uses some randomization to avoid degenerate cases, but with a fixed seed to always provide deterministic behavior.
> 
> -- https://doc.rust-lang.org/std/primitive.slice.html#method.sort_unstable
> 
>> 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!
> 
> Rust’s meets that and is MIT or Apache 2.0. The original pdqsort’s also
> does and is under the zlib license. I’m not including alloca() free,
> because that’s a nonsense restriction that would forbid any local
> variables.

--HPS