What is the space complexity of quicksort?

Question

What is the space complexity of quicksort?

I was doing some research and found some saying it is $O(1)$, some saying it's $O(\log n)$, and some saying $O(n)$. Not sure what to believe, even though $O(\log n)$ seems to make the most sense for me. Does it all depend on the pivot point that is chosen?

Answer 1

Here is quicksort in a nutshell:

• Choose a pivot somehow.
• Partition the array into two parts (smaller than the pivot, larger than the pivot).
• Recursively sort the first part, then recursively sort the second part.

Each recursive call uses $O(1)$ words in local variables, hence the total space complexity is proportional to the height of the recursion tree.

The height of the recursion tree is always at least $\Omega(\log n)$, hence this is a lower bound on the space complexity. If you choose the pivot at random or using a good heuristic, then the recursion tree will have height $O(\log n)$, and so the space complexity is $\Theta(\log n)$. If the pivot can be chosen adversarially, you can cause the recursion tree to have height $\Theta(n)$, causing the worst-case space complexity to be $\Theta(n)$.

Answer 2

Since worst case space complexity of $\Theta(n)$ could be a problem, you can make a slight modification to the Qicksort algorithm: Partition the array, then sort the smaller half recursively, and sort the larger half iteratively. Roughly:

Sort (range r)
    While r contains two or more elements
        Partition range r
        Sort (smaller sub partition)
        r = larger sub partition 

This reduces the worst case space required to $\Theta(\log n))$. It does not help with the worst case execution time.