space complexity of merge sort using array

Question

This algorithm is of mergesort, I know this may be looking weird to you but my main focus is on calculating space complexity of this algorithm.

If we look at the recurrence tree of mergesort function and try to trace the algorithm then the stack size will be log(n). But since merge function is also there inside the mergesort which is creating two arrays of size n/2, n/2 , then first should I find the space complexity of recurrence relation and then, should I add in that n/2 + n/2 that will become O(log(n) + n).

I know the answer, but I am confused in the process. Can anyone tell me correct procedure?

This confusion is due to merge function which is not recursive but called in a recursive function

And why we are saying that space complexity will be O(log(n) + n) and by the definition of recursive function space complexity, we usually calculate the height of recursive tree

Merge(Leftarray, Rightarray, Array) {
    nL <- length(Leftarray)
    nR <- length(Rightarray)
    i <- j <- k <- 0
    while (i < nL && j < nR) {
        if (Leftarray[i] <= Rightarray[j])
            Array[k++] <- Leftarray[i++]
        else
            Array[k++] <- Rightarray[j++]
    }
    while (i < nL) {
        Array[k++] <- Leftarray[i++]
    }
    while (j < nR) {
        Array[k++] <- Rightarray[j++]
    }    
}  

Mergesort(Array) {
    n <- length(Array)
    if (n < 2)
        return
    mid <- n / 2
    Leftarray <- array of size (mid)
    Rightarray <- array of size (n-mid)
    for i <- 0 to mid-1
        Leftarray[i] <- Array[i]
    for i <- mid to n-1
        Right[i-mid] <- Array[mid]
    Mergesort(Leftarray)
    Mergesort(Rightarray)
    Merge(Leftarray, Rightarray) 
}

A mergesort implementation should allocate *one* scratch array of size N or N/2, and then reuse the same scratch array for ALL of the merges. — Matt Timmermans, Oct 20 '18 at 03:42
**Error:** "*Rightarray*" is not defined... (usual error) Also, if this is C, where are the return types, semi-colons, brackets of *for-loops*, etc.? Is this pseudocode?... — Ruks, Oct 20 '18 at 05:13
@suvojit_007 It begs the question, why the C tag if the actual question has absolutely *nothing* to do with C. — WhozCraig, Oct 20 '18 at 05:19
Possible duplicate of [Merge sort space and time complexity](https://stackoverflow.com/questions/30170183/merge-sort-space-and-time-complexity) — awiebe, Oct 20 '18 at 05:21

score 5 · Accepted Answer · answered Nov 16 '18 at 18:47

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).

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.

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

Then it merge upwards

which is 34 < 3n. Then it merge upwards

36 < 16 * 3 = 48

then it merge upwards

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

in a larger case, n = 64

which is 64*3 <= 3*n = 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:

Shamelessly copied from here? https://stackoverflow.com/questions/10342890/merge-sort-time-and-space-complexity — SKPS, Apr 13 '23 at 16:46

score 1 · Answer 2 · answered Oct 20 '18 at 06:51

1

This implementation of MergeSort is quite inefficient in memory space and has some bugs:

the memory is not freed, I assume you rely on garbage collection.
the target array Array is not passed to Merge by MergeSort.

Extra space in the amount of the size of the Array is allocated by MergeSort for each recursion level, so at least twice the size of the initial array (2*N) is required, if the garbage collection is optimal, for example if it uses reference counts, and up to N*log2(N) space is used if the garbage collector is lazy. This is much more than required, as a careful implementation can use as little as N/2 extra space.

answered Oct 20 '18 at 06:51

chqrlie

131,814
10
121
189

if i am not passing the target array to merge function than how can this affect the space complexity? Those statements take same memory whether you execute them in merge or mergesort – newby Oct 20 '18 at 09:10
will memory not be freed automatically for leftarray and rightarray when the recursive call finishes for that particular function say in any step between the execution of program Then it will be very much inefficient with respect to space and there will be large number of memory loacation that will be allocated for left and right subarrays(for every recursive call) Is i am right ? or you want to say something else – newby Oct 20 '18 at 09:28
I am eagerly waiting for you to be online so that you can answer my question thanku very much in advance, I got your point but i have small above doubts please help – newby Oct 20 '18 at 12:30
@newby: not passing the target array to `Merge` is just a mistake, the function does expect a third argument. You originally tagged your question as `c`, allocated objects are not freed automatically in C, unlike Java, you must free them explicitly when they are no longer needed. Regarding the number of allocations, you are definitely making too many calls: a more efficient version would allocate a single temporary array and pass it to an auxiliary function `MergeSortInternal` that would call itself recursively. This would reduce the space complexity to **O(N)** in a single allocation call. – chqrlie Oct 20 '18 at 12:50

space complexity of merge sort using array

2 Answers2