Czytałem artykuły opisujące, w jaki sposób można zmniejszyć złożoność przestrzeni szybkiego sortowania za pomocą rekurencyjnej wersji ogona, ale nie jestem w stanie zrozumieć, jak to jest. Poniżej znajdują się dwie wersje:

QUICKSORT(A, p, r)
       q = PARTITION(A, p, r)
       QUICKSORT(A, p, q-1)
       QUICKSORT(A, q+1, r)


TAIL-RECURSIVE-QUICKSORT(A, p, r)
   while p < r
      q = PARTITION(A, p, r)
      TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
      p = q+1

(Źródło -http://mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html)

O ile rozumiem, oba z nich spowodowałyby wywołania rekurencyjne zarówno po lewej, jak i po prawej stronie tablicy. W obu przypadkach tylko jedna połowa byłaby przetwarzana w tym samym czasie i dlatego w dowolnym momencie tylko jedno wywołanie rekurencyjne używałoby przestrzeni stosu. Nie jestem w stanie zobaczyć, jak rekurencyjny szybki quicksort ogona oszczędza miejsce.

Powyższy pseudo kod pochodzi z artykułu -http://mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html Wyjaśnienie podane w artykule jeszcze bardziej mnie myli -

Quicksort partycjonuje pod-tablicę i kontynuuje dwukrotną rekurencję; jeden na lewej pod-tablicy i jeden po prawej. Każde z tych rekurencyjnych wywołań będzie wymagało własnego indywidualnego strumienia przestrzeni stosu. Ta przestrzeń służy do przechowywania zmiennych indeksujących dla tablicy na pewnym poziomie rekurencji. Jeśli wyobrażamy sobie to od początku do końca wykonania, widzimy, że przestrzeń stosu podwaja się na każdej warstwie.

Jak więc to wszystko naprawi Tail-Recursive-Quicksort?

Cóż, zamiast rekurencji na dwóch pod macierzach, powtarzamy teraz tylko na jednym. Eliminuje to potrzebę podwajania przestrzeni stosu na każdej warstwie wykonania. Omawiamy ten problem, wykorzystując pętlę while jako kontrolę iteracyjną, która wykonuje to samo zadanie. Zamiast potrzebować stosu do zapisywania zestawów zmiennych dla dwóch wywołań rekurencyjnych, po prostu zmieniamy ten sam zestaw zmiennych i używamy pojedynczego wywołania rekurencyjnego dla nowych zmiennych.

Nie widzę, jak przestrzeń stosu podwaja się na każdej warstwie wykonania w przypadku zwykłego szybkiego sortowania.

Uwaga: - W artykule nie ma wzmianki o optymalizacji kompilatora.