# What is the space complexity of quicksort?

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?

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)$$.

• Thank you for this explanation
– Mj _
Mar 31, 2021 at 10:14
• What do you mean by 'adversarially'?
– Mj _
Mar 31, 2021 at 10:18
• If an adversary whose goal is to foil the algorithm chooses the pivots, then it can force the recursion tree to have depth $\Omega(n)$. Mar 31, 2021 at 10:29

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.

• (Brilliantly presented but for calling smaller and larger partitions halves.) Apr 1, 2021 at 5:14