MergeSort time Complexity is O(nlgn) which is a fundamental knowledge. Merge Sort space complexity will always be O(n) including with arrays. If you draw the space tree out, it will seem as though the space complexity is O(nlgn). However, as the code is a Depth First code, you will always only be expanding along one branch of the tree, therefore, the total space usage required will always be bounded by O(3n) = O(n).

2023 October 24th update: There's a question on how I came up with 3n upper bound. My explanation in the comment and re-pasted here. The mathematical proof for 3n is extremely similar to why the time complexity of buildHeap from an unsorted array is upper bounded by 2n number of swaps, which takes O(2n) = O(n) time. In this case, there's always only 1 additional branch. Hence, think of it as doing the buildHeap again for 1 additional branch. Hence, it will be bounded by another n, having a total upper bound of 3n, which is O(3n) = O(n). note that in this case, we're using the similar mathematics from buildHeap(inputArray) time complexity to prove the space complexity of single threaded mergeSort instead of time complexity. I can write up a full rigorous math proof for this when I have time.

• How can building a heap be O(n) time complexity?

For example, if you draw the space tree out, it seems like it is O(nlgn)

                             16                                 | 16
                            /  \                              
                           /    \
                          /      \
                         /        \
                        8          8                            | 16
                       / \        / \
                      /   \      /   \
                     4     4    4     4                         | 16
                    / \   / \  / \   / \
                   2   2 2   2.....................             | 16
                  / \  /\ ........................
                 1  1  1 1 1 1 1 1 1 1 1 1 1 1 1 1              | 16

where height of tree is O(logn) => Space complexity is O(nlogn + n) = O(nlogn). However, this is not the case in the actual code as it does not execute in parallel. For example, in the case where N = 16, this is how the code for mergesort executes. N = 16.

                           16
                          /
                         8
                        /
                       4
                     /
                    2
                   / \
                  1   1

notice how number of space used is 32 = 2n = 2*16 < 3n

Then it merge upwards

                           16
                          /
                         8
                        /
                       4
                     /  \
                    2    2
                        / \                
                       1   1

which is 34 < 3n. Then it merge upwards

                           16
                          /
                         8
                        / \
                       4   4
                          /
                         2
                        / \ 
                       1   1

36 < 16 * 3 = 48

then it merge upwards

                           16
                          / \
                         8  8
                           / \
                          4   4
                             / \
                            2   2
                                /\
                               1  1

16 + 16 + 14 = 46 < 3*n = 48

in a larger case, n = 64

                     64
                    /  \
                   32  32
                       / \
                      16  16
                          / \
                         8  8
                           / \
                          4   4
                             / \
                            2   2
                                /\
                               1  1

which is 643 <= 3n = 3*64

You can prove this by induction for the general case.

Therefore, space complexity is always bounded by O(3n) = O(n) even if you implement with arrays as long as you clean up used space after merging and not execute code in parallel but sequential.

Example of my implementation is given below:

templace<class X> 
void mergesort(X a[], int n) // X is a type using templates
{
    if (n==1)
    {
        return;
    }
    int q, p;
    q = n/2;
    p = n/2;
    //if(n % 2 == 1) p++; // increment by 1
    if(n & 0x1) p++; // increment by 1
        // note: doing and operator is much faster in hardware than calculating the mod (%)
    X b[q];

    int i = 0;
    for (i = 0; i < q; i++)
    {
        b[i] = a[i];
    }
    mergesort(b, i);
    // do mergesort here to save space
    // http://stackoverflow.com/questions/10342890/merge-sort-time-and-space-complexity/28641693#28641693
    // After returning from previous mergesort only do you create the next array.
    X c[p];
    int k = 0;
    for (int j = q; j < n; j++)
    {
        c[k] = a[j];
        k++;
    }
    mergesort(c, k);
    int r, s, t;
    t = 0; r = 0; s = 0;
    while( (r!= q) && (s != p))
    {
        if (b[r] <= c[s])
        {
            a[t] = b[r];
            r++;
        }
        else
        {
            a[t] = c[s];
            s++;
        }
        t++;
    }
    if (r==q)
    {
        while(s!=p)
        {
            a[t] = c[s];
            s++;
            t++;
        }
    }
    else
    {
        while(r != q)
        {
            a[t] = b[r];
            r++;
            t++;
        }
    }
    return;
}

The cost of mergesort implemented classically either as a top-down recursive function or a bottom-up iterative with a small local array of pointers is the same: O(N.log(N)). The number of comparisons will vary depending on the actual contents of the array, but by at most a factor of 2.

You can improve this algorithm at a linear cost by adding an initial comparison between the last element of the left slice and the first element of the right slice in the merge phase. If the comparison yields <= then you can skip the merge phase for this pair of slices.

With this modification, a fully sorted array will sort much faster, with a linear complexity, making it the best case, and a partially sorted array will behave better as well.