What happened if we implement quicksort without tail recursion?

On Wikipedia, it said that


The in-place version of quicksort has a space complexity of $\mathcal{O}(\log n)$, even in the worst case, when it is carefully implemented using the following strategies:

• in-place partitioning is used

• After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most $\mathcal{O}(\log n)$ space. Then the other partition is sorted using tail recursion or iteration, which doesn't add to the call stack.

Below is naive quick sort:

Quicksort(A, p, r)
{
 if (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  Quicksort(A, q+1, r)
 }
}

Below is tail recursion quick sort:

Quicksort(A, p, r)
{
 while (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  p: <- q+1
 }
}

Algorithms above are based on this link

What if we just use in place partitioning? Is it not enough to make quicksort having space complexity of $\mathcal{O}(\log n)$?

Below is what I understand of stack call of quicksort. Do I misunderstand it?

Suppose I have sequence of number: $\{3, 5, 2, 7, 4, 1, 8, 6\}$. I use in place method in this case.

input    : 5   3   2   7   4   1   8   6
partition: 3   2   4   1  (5)  7   8   6
stack 1  : 2   1  (3)  4
stack 2  : 1  (2)
stack 3  : 1                               - stack 3 removed
stack 2  : 1  (2)                          - stack 2 removed
stack 1  : 1   2  (3)   4
stack 2  :              4                  - stack 2 removed
stack 1  : 1   2  (3)   4                  - stack 1 removed
input    : 1   2   3   4  (5)  7   8   6
stack 1  :                    (6)  7   8
stack 2  :                        (7)  8
stack 3  :                             8   - stack 3 removed
stack 2  :                        (7)  8   - stack 2 removed
stack 1  :                    (6)  7   8   - stack 1 removed
input   : 1   2   3   4   5   6   7   8 -> sorted

We need $3$ stacks at most, which is $$\log(n) = \log(8) = 3$$

If what I told

You're correct that your version with a loop doesn't guarantee O(log n) additional memory. The problem is that you have recursively sorted the partition "on the left". You ignored:


the partition with the fewest elements is (recursively) sorted first

This is essential. It ensures that each time you make a recursive call (and lay down a new stack frame, requiring constant additional memory), the sub-array that you are sorting is at most half the size of sub-array being sorted at the previous stack level. Therefore the maximum depth of the recursion is the base-2 log n, which gives the desired bound on memory use.

In your code you permit a worst case in which you recursively sort the larger partition, having size only one smaller than the previous at each step. Then indeed the recursion depth can be n.

The way to make the code entirely iterative, with no call-recursion at all, is (as always) to use a stack data structure instead of the call stack. So instead of recursively calling to sort the small partition, you push the large partition on to the stack (by which I mean, push a pair of integers describing its location in the array) and loop around to continue sorting the small partition. When the size of the piece you're working on hits 1 you pop the stack and loop around to continue sorting that.

StackExchange Computer Science Q#35592, answer score: 2