W dniu 2015-07-15 o 23:37, bartekltg pisze:
> W pewnym przypadkach i mnimalnie. Potrzebujesz dodatkowej pamięci.
> Chyba nawet w Cormenia było;-) Tworzy sie stos z wrzucanymi na niego
> elementami podziału.

Widziałem implementacje w Pascalu zwykłego Qsorta i iteracyjnego.
Iteracyjny był znacząco szybszy. Nie bez powodu stosuje się w programach
funkcje inline aby nie mieć narzutu na wołanie procedury. W
rekurencyjnej metodzie nie można zrobić inline natomiast mamy tam masę
wywołań. Poza tym łatwiej jest zaimplementować pasek postępu dla
długiego sortowania.

> W ząden sposób nie zapobiega to przypadkowi złego działąnia qsorta.
> Wiec tablica musi mieć w praktyce długość rzędu długości danych.

W procedurze pascalowej była tablica rzędu 40-tu par i nigdy się do tej
granicy nie zbliżało, był pewien zapas. Dla kilu milionów 20 w
zupełności wystarczało, trzeba było mniej tablicy niż log2(N).
Zostaje przypadek złośliwy, ale wtedy lepiej przełączyć się na heapsort
zamiast zwiększać tablicę.