Is Quicksort in-place or not? [duplicate]

Question

So the space efficiency of Quicksort is O(log(n)). This is the space required to maintain the call stack.

Now, according to the Wikipedia page on Quicksort, this qualifies as an in-place algorithm, as the algorithm is just swapping elements within the input data structure.

According to this page however, the space Efficiency of O(log n) disqualifies Quicksort from being in place, as it's space efficiency is greater than O(1). According to this definition any algorithm with space efficiency greater than O(1) is not in-place. So I assume this means that all recursive algorithms are by definition not in place?

So obviously there are two different definitions of in-place here. Wikipedia is not always an entirely reliable source, so I consulted with one of my professors.

My professor agreed with the second definition. He said Quicksort is not in-place. Even though the data remains in the input array, the extra space needed for the stack disqualifies it. My professor wrote a popular book on Algorithms so I respect his opinion greatly, but this answer just does not seem correct to me.

I see the property of in-place as being quite literal. The data stays in place. It does not move from it's original data structure. To me, this definition is more useful, because it means you can perform your algorithm with pointers instead of requiring you to copy data. This seems like a valuable property of an algorithm and worthy of the name "in-place".

Answer 1

Intro to Algorithms from MIT Press qualifies QuickSort as in-place - it sorts the elements within the array with at most a constant amount of them outside the array at any given time.

At the end of the day, people will always have differing opinions (is Top-Down Memoization considered Dynamic Programming? Not to some "classical" folks), side with who you trust the most. I trust the editors and the authors at MIT Press (along with my professor, who qualifies it as in-place).

Typically, the problem with QuickSort is not that it doesn't sort in-place, but that it is not stable - satellite data is not kept in order.

Edit

Kuroi's point highlights part of this argument I think is very important.

Many argue that it requires O(log(n)) extra memory for recursive calls and the data is leaked in the form of the indices on the stack, however this is negligible for very large sizes of N (log(1,000,000,000) =~ 30) and it ignores the fact that typically moving data on the heap takes much, much longer, when size(data) >> size(index).

The indices of the data are not the elements themselves - so the elements of the data are not stored outside the array, other than a constant amount of them (in each call).

Answer 2

Strictly speaking Quicksort has a space efficiency of O(n) since the degenerate case would require an index on the stack for each element of the array. Though on average it will be O(log(n)). Given that I don't think there is any way you could call it an "in place" algorithm, unless you go with a degenerate definition of "in place" meaning that the original data is not stored outside of the original array bounds (excluding copy/swap operations).

This definition of "in place" would be degenerate because you could take any "out of place" algorithm and make it satisfy this "in place" requirement by having it do all of its extra data storage use pointers to the original array. Then when the answer is found you could reorder the original array "in place" using the pointer data.

Answer 3

qsort does indeed swap data in place, but the stack space used for recursion is in log₂(N).

These two properties are not contradictory. Usually "in place" refers to heap memory, i.e. what you must explicitely allocate for the algorithm to work.

However, a logarithmic space complexity is basically neglectible, except in pathological cases (say you want to do a quicksort on a 8 bits microcontroller with 512 bytes of stack :)).