Skip site navigation (1)Skip section navigation (2)
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>