Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm.]

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