Problem
The algorithm creates a new array each step that is the same size as the original.
The algorithm creates two variables for every element in the array.
Recursion adds space equal to the recursion depth, but the array size halves each time it recurses.
Each recursive step stays in memory until the entire algorithm completes.
Why is the average space complexity of an in-place, recursive quicksort O(log n) instead of O(1)?