title: space complexity of merge sort in python
body: <p>when I implement a merge sort in python, I doubt that the auxiliary space complexity is O(logn) which is documented is most analysis (account for the call stack in recursion) if I implement in Python based on the following scripts. merge_sorted_list has been ignored.</p>
  
  <pre><code>def merge_sort(mylist):
      print("splitting ",mylist)
      if (len(mylist) &gt; 1):
  
          mid = len(mylist)/2
  
          mylist[:mid] = merge_sort(mylist[:mid])
          mylist[mid:] = merge_sort(mylist[mid:])
  
          mylist[:] = merge_sorted_list(mylist[:mid],mylist[mid:])
  
      return mylist
  </code></pre>
  
  <p>As in Python, I found that calling <strong>merge_sort(mylist[:mid])</strong> would create a new list of the sliced part. Therefore, it is not totally in-place manipulation. If I write in this way, would my space complexity become O(n*logn)? I am not sure about my statement but if true, is there anyway to reduce to O(logn) in Python (I know in java array we don't have this problem)? Thank you sincerely.</p>