Date: Wed, 19 Apr 2023 22:28:22 +0000 From: Colin Percival <cperciva@tarsnap.com> To: Hans Petter Selasky <hselasky@freebsd.org>, 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: <010001879ba20fa7-95ae06cc-e046-4f59-a9b7-5e2cd389d101-000000@email.amazonses.com> In-Reply-To: <42d63675-9b1f-70dc-a1da-fef3d43790fd@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> <42d63675-9b1f-70dc-a1da-fef3d43790fd@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On 4/19/23 14:41, Hans Petter Selasky 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. > > 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! Quicksort with cryptographically randomized pivot selection is O(N^2) worst case but O(N log N) average-case-for-worst-case-inputs which is good enough for most purposes. Quicksort with in-place median-of-medians pivot selection is O(N log N) worst case. Both of them can be easily implemented with O(log N) extra space (for the call stack), and with O(1) extra space if you're insane enough to care. -- Colin Percival FreeBSD Deputy Release Engineer & EC2 platform maintainer Founder, Tarsnap | www.tarsnap.com | Online backups for the truly paranoid
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?010001879ba20fa7-95ae06cc-e046-4f59-a9b7-5e2cd389d101-000000>