What is the worst-case auxiliary (call-stack) space complexity of an in-place…

In tail-call optimization, a recursive call that is the last operation in a function can be converted into a loop, so it costs no extra stack frame. For divide-and-conquer recursion this alone does not bound the stack depth -- the depth is bounded only when the call that keeps its stack frame (the non-tail, 'real' recursive call) is always made on the smaller of the two subproblems, while the larger subproblem is handled by the tail-called/looped branch. Since each such non-tail call operates on at most half the elements of its parent call, the recursion depth is bounded by log2(n).

For Quick Sort on an array of size n, each partitioning step splits the array into two parts around the pivot. A tail-recursive implementation always makes the real (stack-consuming) recursive call on whichever part is smaller, and turns the call on the larger part into a loop. So the sequence of 'real' call sizes is at most n, n/2, n/4, ..., 1 -- at most log2(n) levels before a base case is reached. The maximum number of stack frames alive at any time, i.e. the auxiliary space, is therefore O(log n).

Cross-check with the unoptimized case: a naive recursive Quick Sort that keeps a stack frame for BOTH recursive calls at every level (or always keeps the frame for a fixed side regardless of its size) can, under a heavily skewed partition (sizes 0 and n-1 repeated), build a chain of n nested frames -- the well-known O(n) worst-case space bound of ordinary recursive Quick Sort. Since always recursing into the smaller half halves the segment size at every level instead, the bound tightens from O(n) to O(log n), confirming that O(log n) is the space complexity of this tail-recursive implementation.