Search code examples
sortingcomplexity-theoryspace-complexity

merge sort space

In a top-down merge sort the recursive functions are called in this fashion:

void mergesort(Item a[], int l, int r) {
    if (r <= l) return;
    int m = (r+l)/2;
    mergesort(a, l, m);
    mergesort(a, m+1, r);
    merge(a, l, m, r);
}

It is given in text book that space complexity of this strategy is O(n). whereas if we look at the recursion closely : we are passing pointer to array in recursive calls. Second the recursion is resolved in preorder order of traversal by merging bottom nodes to parent nodes. so at each time there are O(logn) variables on stack (or O(log n) frames on stack). So how is it that space complexity is O(n) inspite of having in-place merging techniques?

Solution

  • You are right that the space taken up by the recursive calls is O(log n).

    But the space taken by the the array itself is O(n).

    The total space complexity is O(n) + O(log n).

    This is O(n), because it is bounded above by (n)=>2(n).