Memory complexity of Quicksort

Question

The space complexity of Quicksort is listed as O(logn).

however - Quicksort can process without use of any additional memory: at each iteration, during the partition process, the entries are swapped eventually to be in the left and right partitions based on the pivot used. this recursive swapping-and-thus-forming-the-partitions can be done on the list itself without having the partitions at one level of recursive calls interfering and without quicksorting in different levels of calls interfering.

What's the use for extra memory in Quicksort?

TIA.

//============================

EDIT:

agree with stack space in the comments/answers-- had missed that.

still,

Quicksort performs in O(nlogn) time in the expected case-- by forming (nearly) equal-size partitions at each level of recursion.

the stack-space used is a binary tree, full tree in the optimum case, with height log n. Each node on this tree is a recursive call, and the stack-space in this case is on the order of n-- not log n. there are O(n) nodes on this tree. the recursive calls to the left and right partitions are being done simultaneously-- the call tree is full at a certain point of execution.

so- the average case space complexity should be O(n)-- not O(logn) (?)

it also contradicts with the space complexity of merge-sort. merge-sort space complexity is listed as O(n) and processes similarly.

Answer 1

Quicksort normally uses O(log n) extra memory, stored on the stack. It's not O(n), because the binary tree is never explicit in memory, we just do a post-order traversal of it (that is: only one path in the tree is ever stored at a given time).

Mergesort is listed as O(n) because we usually copy the result of the merge into a new array. In-place sorting is possible, but increases the time complexity to O(n log² n), according to Wikipedia. It would still use O(log n) for the recursion.