Space Complexity of Quick Sort

Question

Is Quick Sort an in-place algorithm?

I read somewhere that although its space complexity is O(logn) [best case], it is referred to as an in place algo by Wikipedia because it involves just swapping of elements.

What is Correct?

Answer 1

Quick sort is an in place sorting algorithm

Explanation -

Any algorithm that does not require any additional memory (other that constant size variable memory ) is referred as in place algorithm

Eg. In case of quick sort or in case of bubble sort, the sorting is done by swapping the variables internally within the given array. Thus making the algorithm in place

Where as in case of merge sort, an additional array (memory) is needed. Thus merge sort is not in place algorithm

Comments

O(logn) space is that of the stack. Since quick sort is recursive, implicit stack is bound to be there for function calls. However, explicit memory is not needed, unlike in merge sort, which uses an explicit array to sort numbers. Hence, it is in-place.