Merge sort space and time complexity

Question

Given the following merge sort algorithm :

mergesort(A,p,r) 

    if (r <= l) return    //constant amount of time
    int m = (p+r)/2       //constant amount of time

    mergesort(A, p, q)      // these two calls will decide the
    mergesort(A, q+1, r)    // O(logn) factor inside O(n * logn) right?

    merge(A, p, q, r)       lets dwell further


merge(a,p,q,r){

    n1 = q-p+1         //constant time
    n2 = r-q           //constant time

    // Let L[1...n1+1] and R[1...n2+1] be new arrays    // idk , lets say constant

    for i,j in L[],R[]
        L[i] = A[p+i-1]
        R[j] = A[q+j]  // shouldn't this take time varying on size of array?
                       // also extra space too?

    i=1 j =1           // constant time

    for k = p to r     // everything below this will contribute to O(n)
                       // inside O(n*logn) amirite?
        if L[i]<=R[j]
            A[k] = L[i]
            i++

        else A[k] = R[j]
             j++

How come we are estimating O(nlogn) time complexity for it , keeping in mind that there are left and right arrays being created to be merged back?

And how come space complexity is O(n) only if extra size is being used? Won't the two of them be increased by n, because filling up array takes O(n) and L[] and R[] are being created at each recursion step.

Answer 1

I suggest you reason about this by drawing a tree on paper: first write down your whole array:

2 4 7 1 4 6 2 3 7 ...

Then write what the recursion causes it to be split in below it:

 2 4 7 1 3 4 6 2 3 7 ...

          |
2 4 7 1 3   4 6 2 3 7 ...

    |            |
2 4   7 1 3  4 6   2 3 7

And so on with each piece.

Then, count how many rows you've written. This will be close to the base 2 logarithm of the number of elements you started with (O(log n)).

Now, how much work is being done for each row? It's O(n). Merging two arrays of lengths n1, n2 will take O(n1 + n2), even if you have to allocate space for them (and you don't in a proper implementation). Since each row in the recursion tree has n array elements, it follows that the work done for each row is O(n) and therefore the entire algorithm is O(n log n).

And how come space complexity is O(n) only if extra size is being used? Won't the two of them be increased by n , because filling up array takes O(n) and L[] and R[] are being created at each recursion step.

This is more interesting. If you do indeed create new L, R arrays at each recursion step, then the space complexity will be O(n log n). But you don't do that. You create one extra array of size n at the beginning (think of it as a global variable), and then you store the result of each merge into it.

You only pass around things that help you identify the subarrays, such as their sizes and the indexes they begin at. Then you access them using the original array and store the result of the merge in the globally allocated array, resulting in O(n) extra space:

global_temp = array of size equal to the array you're sorting
merge(a,p,q,r){

    i=p 
    j =q              // constant time

    while i < q and j <= r // or a similar condition       
        if A[i]<=A[j]
            global_temp[k++] = A[i]
            i++

        else 
            global_temp[k++] = A[j]
            j++
     // TODO: copy remaining elements into global_temp
     // TODO: copy global_temp into A[p..r]

Answer 2

Your question is unclear, but perhaps you are confused by the extra space you need.

Obviously, on the first pass (and every pass) you read the entire data, and merge each partition into one twice as big.

Let's just focus on 8 elements.

8 7 6 5 4 3 2 1

In the first pass, the size of each partition is 1, and you are merging them to size=2. So you read the 8 and the 7, and merge them into a partition:

7 8     5 6     3 4     1 2

The next stage is to merge groups of 2 into groups of 4. Obviously, you have to read every element. So both of these passes take O(n) operations. The number of times to double is log2(n), which is why this algorithm is O(n log n)

In order to merge, you need extra room. You could recycle it. But the worst case is when you merge two n/2 partitions into n (the last time). The easy way to envision that is to allocate a buffer big enough to copy the entire data into. That would be O(n) storage.

5 6 7 8        1 2 3 4
i              j
EMPTY Buffer int buf[8]
k = 0
buf[k++] = (orig[j] < orig[i]) ? orig[j++] : orig[k++]