Date: Wed, 19 Apr 2023 23:17:54 +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: <ZEBagv961lutuBJV@bec.de> In-Reply-To: <e2ea5c89-aa48-e257-b9d5-7fe783bf216e@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>
next in thread | previous in thread | raw e-mail | index | archive | help
Am Wed, Apr 19, 2023 at 09:27:14PM +0200 schrieb Hans Petter Selasky: > > > qsort() is frequently used to do all kinds of sorting, and some pointed out that qsort() can technically be any kind of sorting algorithm, but looking around it is not. > > > > Because there are variants that are guaranteed n log n? Which is better > > than your n log^2 n. > > Only so-called mergesort() algorithms can do sorting in O(N log N) time, > from what I know. 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. Joerg
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?ZEBagv961lutuBJV>