Date: Thu, 20 Apr 2023 08:32:54 +0200 From: Hans Petter Selasky <hselasky@freebsd.org> To: Colin Percival <cperciva@tarsnap.com>, 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: <1ce00b7b-e34b-a91b-59ef-c3ee9683c4a0@freebsd.org> In-Reply-To: <010001879ba20fa7-95ae06cc-e046-4f59-a9b7-5e2cd389d101-000000@email.amazonses.com> 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> <010001879ba20fa7-95ae06cc-e046-4f59-a9b7-5e2cd389d101-000000@email.amazonses.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On 4/20/23 00:28, Colin Percival wrote: > > 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. Yes, I know there are different ways to mitigate O(N^2) behaviour, but there is not yet after xxx years of research a way to fully mitigate that behaviour. What I think, there should be some statistics done in our qsort() when it goes to O(N^2), and then it could fallback to bsort() for example, to avoid issues with malloc(). Or maybe one round of bsort() is enough to make qsort() do its thing right. I want to investigate that. Like a hybrid. --HPS
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?1ce00b7b-e34b-a91b-59ef-c3ee9683c4a0>