Qunado ele faz refeência a memória, ele está querendo dizer o tamanho da pilha de execução. Ou seja, cada vez que chammos a recursão uma nova função é achamada e o consumo de memória aumenta. Pra resolver esse problema, vamos sempre iniciar a recursão na menor parte:
QUICKSORTE2 (A, p, r)
meio = (p+r)/2
enqunato p < r
q <- particiona(A, p, r)
se q >= meio
QUICKSORTE2 (A, p, q-1)
p <- q + 1
senao
QUICKSORTE2 (A, q+1, r)
r <- q - 1
Note que o pior caso para a memória com esse algorítmo não será quando q estiver na posição r-1. O pior caso vai se dar quando q se encontrar no meio. Nesse caso (M é a qunatida de memória):
$$M(1) = 1$$ $$M(n) = O(n) + M(n/2)$$
Desenvolvendo pelo método da substitituição:
$$M(n) = an + M(n/2) = an + an/2 + M(n/2) = \sum_{j = 1}^{i} \frac{an}{2^{i-1}} + M(\frac{n}{2^i})$$
$$M(n) = an \cdot \frac{1/2^i - 1}{1/2-1} + M(\frac{n}{2^i})$$
Suponha que n seja multiplo de 2, ou seja, $n = 2^i$. Dessa forma:
$$M(n) = a \cdot \frac{1 - n}{1/2-1} + M(1) = 2a \cdot \frac{1 - n}{-1} = 1 + 2a \cdot (n - 1)$$
Vaja que no pior caso o nosso consumo de memória vai ser linear.