title: Is Quicksort in-place or not?
body: <p>So the space efficiency of Quicksort is O(log(n)). This is the space required to maintain the call stack. </p>
  
  <p>Now, according to the <a href="https://en.wikipedia.org/wiki/Quicksort">Wikipedia page on Quicksort</a>, this qualifies as an in-place algorithm, as the algorithm is just swapping elements within the input data structure.</p>
  
  <p><a href="https://en.wikipedia.org/wiki/In-place_algorithm">According to this page</a> 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?</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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".</p>