Why does QuickSort use O(log(n)) extra space?

Solution 1:

Correct, the extra space are the log(n) stack frames. From the Wikipedia article of Quicksort:

There is a more complex version which [...] can achieve the complete sort using O(log n) space (not counting the input) on average (for the call stack).

While you could implement quicksort iteratively (i.e., using a loop instead of recursion), you would then need to maintain an auxiliary stack, because Quicksort has two recursive calls and not just one.

Finally, as other answers have pointed out, O(log(n)) is for pretty much all practical applications very, very small. Every constant factor, like the overhead of your data structure, will have a greater impact on memory usage.

Solution 2:

To get rid of the recursive call you would have to use a stack data structure in your code, and it would still occupy log(n) space.

Solution 3:

If you read further in the Wikipedia article, you will find a more thorough discussion of space complexity. In particular, they write:

Quicksort with in-place and unstable partitioning uses only constant additional space before making any recursive call. Quicksort must store a constant amount of information for each nested recursive call. Since the best case makes at most O(log n) nested recursive calls, it uses O(log n) space. However, without Sedgewick's trick to limit the recursive calls, in the worst case quicksort could make O(n) nested recursive calls and need O(n) auxiliary space.

Practically speaking, O(log n) memory is nothing. For instance, if you were to sort 1 billion ints, storing them would require 4 GB, but the stack would only require about 30 stack frames, at something like 40 bytes, so about 1200 Bytes in total.