title: Why space complexity of heap sort is O(1)?
body: <p>I don't understand how the space complexity of heap sort is O(1)? Though, quick sort doesn't use any extra array (i.e. in-place), its space complexity is O(n) in worst case and O(lg n) in best case as a stack is used at back end for recursive calls. Am I right?</p>
  
  <p>The same goes with heap sort. Though, it is in-place, but since, Build-Heap function calls Max-Heapify function, so it's space complexity should be equal to Max-Heapify, i.e. O(lg n). Isn't it? Also, later on Max-Heapify function is called at root node for n times and as I said Max-Heapify() space complexity is O(lg n).</p>
  
  <p>So, overall space complexity of Heap sort should be O(lg n). But I found it O(1) on wikipedia. Help me understand it.</p>