Date: Wed, 19 Apr 2023 23:47:35 +0200 From: Hans Petter Selasky <hps@selasky.org> To: Joerg Sonnenberger <joerg@bec.de>, dev-commits-src-all@freebsd.org Subject: Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm. Message-ID: <b9395dbc-bddf-6250-0185-14ae4318bcb2@selasky.org> In-Reply-To: <ZEBagv961lutuBJV@bec.de> 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>
next in thread | previous in thread | raw e-mail | index | archive | help
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. They keep track of the sorting cost, and then at some point give up, finding a good median. So called radix sorting is more appropriate for doing split partition sorting, where you have not just +1/0/-1 as return values from the compare() callback function, but an actual N-bit indexer. This limits the complexity and recursion. Sometimes when you know the data to be sorted well, qsort() works great, but other times not. And there should be more options in FreeBSD, in my opinion. --HPS
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?b9395dbc-bddf-6250-0185-14ae4318bcb2>