In both articles, the complexity of the space to which they relate refers to extra space (not counting the space needed to store the original array). This extra space can be obtained from the call stack in addition to the usual case when an additional array is declared. Each recursive call creates a stack stack in the call stack, which occupies a space, and the number of stack frames depends on the size of input n , so it must be taken into account.
Let's use the Wikipedia article for reference, as the blog is completely incompatible as @Jim Mischel pointed out.
For quick sorting in place, a change from a naive implementation will give O(log n) extra space on average , instead of O(n) extra space (in all cases) in a naive implementation. The complexity of the worst - case extra space, as indicated by blog 1, is indicated by O(n) when the algorithm encounters its worst case (sorted list; be n recursive calls, so the call stack will take O(n) extra space).
1 : (Thanks to @rici for pointing out) However, the blogger is right if we expect an implementation without optimization, as stated in the Wikipedia article . In the worst case, the algorithm can be improved to use O(log n) extra space, first recursing into a smaller part and implementing a tail call for the longer part. Since the smaller part is always less than half the input size, there will be no more than O(log n) recursive calls. Assuming tail call optimization, the longer part will reuse the current stack stack without additional spaces. If tail call optimization is not performed, we can always write an iterative implementation with an explicit stack.