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
