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