0

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.

def merge_sort(mylist):
    print("splitting ",mylist)
    if (len(mylist) > 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

As in Python, I found that calling merge_sort(mylist[:mid]) 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.

evehsu
  • 39
  • 4
  • 1
    Where have you seen the space complexity documented as O(log n)? – Oliver Charlesworth Dec 30 '17 at 20:00
  • https://stackoverflow.com/questions/10342890/merge-sort-time-and-space-complexity – evehsu Dec 30 '17 at 23:03
  • just to clarify, the space complexity is O(n) on wiki where I believe this auxiliary space of O(n) was caused in merging step instead of splitting step. However in my split part, I don't think I should only count the call-stack frame as new sliced list would take some memory too. Therefore, I suspect the real space usage for splitting would be O(nlogn). – evehsu Dec 30 '17 at 23:05

0 Answers0