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. Jess >>> 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
