Space Complexity and Tail Recursion
What you'll learn: How quicksort uses O(log n) expected stack space and how tail recursion optimization keeps memory usage minimal.
Why Stack Space Matters in Quicksort
When quicksort runs, each recursive call consumes stack space to store the current state (partition boundaries, return addresses). Even though quicksort is often faster than mergesort, it's important to understand its memory footprint.
Expected space complexity: O(log n)
In the average case with balanced partitions, quicksort's recursion depth is log₂(n). Each level stores a small amount of data, giving us logarithmic space—much better than mergesort's O(n) auxiliary array.
Worst-case space: O(n)
If partitions are extremely unbalanced (one side always has one element), recursion depth becomes n, using linear stack space. This happens with poor pivot choices on already-sorted data.
The Tail Recursion Optimization
Here's the insight: after partitioning, quicksort makes two recursive calls—one for each partition. The second call is tail-recursive (nothing happens after it returns). We can eliminate its stack frame by using iteration instead.
The trick: Always recurse on the smaller partition first, then loop back to handle the larger one. This guarantees recursion depth stays O(log n) even in the worst case.
Think of it like this: if you always tackle the smaller pile of papers first recursively, then handle the bigger pile in your current workspace, you never stack up more than log₂(n) desks, even if the piles are lopsided.
Without this optimization, recursing on the larger partition first could build a deep call stack. By always choosing the smaller side, you ensure each recursive level cuts the problem size by at least half.
Key Takeaway: Quicksort uses O(log n) expected stack space, and by always recursing on the smaller partition first (then handling the larger one iteratively), you can guarantee O(log n) space even in worst-case scenarios.