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

On 4/20/23 08:50, Jessica Clarke wrote:
> On 20 Apr 2023, at 07:26, Hans Petter Selasky <hselasky@freebsd.org> wrote:
>> 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
> 
> That’s not Rust, and that’s also a comment, not a malloc call.
> 
>>>> 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.
> 
> Again. Citation needed. Rust’s documentation says otherwise.

Hi Jessica,

Here are my citations:

cd /usr/ports/lang/rust
make extract
less work/rustc-1.68.2-src/library/alloc/src/slice.rs

     /// The current algorithm is based on [pattern-defeating 
quicksort][pdqsort] 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.

less /usr/src/lib/libc/stdlib/heapsort.c

The first thing heapsort() does is go and grab memory:

>         if ((k = malloc(size)) == NULL)
>                 return (-1);

--HPS