Date: Wed, 19 Apr 2023 23:41:20 +0200 From: Hans Petter Selasky <hselasky@freebsd.org> To: Jessica Clarke <jrtc27@freebsd.org> Cc: Brooks Davis <brooks@freebsd.org>, src-committers <src-committers@freebsd.org>, dev-commits-src-all@freebsd.org, dev-commits-src-main@freebsd.org Subject: Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm. Message-ID: <42d63675-9b1f-70dc-a1da-fef3d43790fd@freebsd.org> In-Reply-To: <2840BE79-CC25-427A-A5E9-476A38E749E3@freebsd.org> References: <202304191206.33JC6Qcp062380@gitrepo.freebsd.org> <ZEAM3rO9r5e97BHE@spindle.one-eyed-alien.net> <a073fd36-9aa9-e988-0cc5-86af305fb654@freebsd.org> <3B5734C4-8630-4CD5-BA8D-DE33899161F1@freebsd.org> <e2ea5c89-aa48-e257-b9d5-7fe783bf216e@freebsd.org> <2840BE79-CC25-427A-A5E9-476A38E749E3@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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. 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! --HPS (*) https://en.wikipedia.org/wiki/Quicksort
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?42d63675-9b1f-70dc-a1da-fef3d43790fd>