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.
Citation needed. This directly contradicts Rust’s documentation: > This sort is unstable (i.e., may reorder equal elements), in-place (i.e., > does not allocate), and O(n * log(n)) worst-case. > > 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. Jess
