Date: Thu, 20 Apr 2023 11:20:05 +0200 From: Joerg Sonnenberger <joerg@bec.de> To: dev-commits-src-all@freebsd.org Subject: Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm.] Message-ID: <ZEEDxY7EnaEKycMF@bec.de> In-Reply-To: <b9395dbc-bddf-6250-0185-14ae4318bcb2@selasky.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> <ZEBagv961lutuBJV@bec.de> <b9395dbc-bddf-6250-0185-14ae4318bcb2@selasky.org>
next in thread | previous in thread | raw e-mail | index | archive | help
Am Wed, Apr 19, 2023 at 11:47:35PM +0200 schrieb Hans Petter Selasky: > On 4/19/23 23:17, Joerg Sonnenberger wrote: > > That's false. The difficult part of QuickSort is the median selection. > > This can be done in O(n) using the median of median algorithm and when > > combined into the main algorithm, much of the work for the median > > selection also helps the partition step. > > Hi Joerg, > > From what I know, they all fall back to other sorting algorithms using > malloc(), in the end. Please, just go and read: Blum, Floy, Pratt, Rivest, Tarjan: Time Bounds for Selection, 1973. [https://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf] If you want a slightly more variant: Alexandrescu: Fast Deterministic Selection, 2017. [http://erdani.org/research/sea2017.pdf] Short answer: QuickSort requires O(log N) extra space, which is essentially a fixed cost given the natural address space limitations. Unless operating in a seriously confined environment, that's a perfectly fine use of the regular stack. Joerg
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?ZEEDxY7EnaEKycMF>