Merge sort time and space complexity

Question

Let's take this implementation of Merge Sort as an example

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

a) The time complexity of this Merge Sort is O(n lg(n)). Will parallelizing (1) and (2) give any practical gain? Theorotically, it appears that after parallelizing them also you would end up in O(n lg(n)). But practically can we get any gains?

b) Space complexity of this Merge Sort here is O(n). However, if I choose to perform in-place merge sort using linked lists (not sure if it can be done with arrays reasonably) will the space complexity become O(lg(n)), since you have to account for recursion stack frame size? Can we treat O(lg(n)) as constant since it cannot be more than 64? I may have misunderstood this at couple of places. What exactly is the significance of 64?

c) Sorting Algorithms Compared - Cprogramming.com says merge sort requires constant space using linked lists. How? Did they treat O(lg(n)) constant?

d) Added to get more clarity. For space complexity calculation is it fair to assume the input array or list is already in memory? When I do complexity calculations I always calculate the "Extra" space I will be needing besides the space already taken by input. Otherwise space complexity will always be O(n) or worse.

this answer would be helpful for some concepts: http://stackoverflow.com/a/35050103/550393 — 2cupsOfTech, Jan 27 '16 at 23:31

score 115 · Answer 1 · edited Dec 24 '22 at 04:16

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 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;
}

@PDN Consider Chee Loong Soon's last graphic in the n=64 case. You can see 2 diagonal lines of `1, 2, 4, 8, 16, 32` where each number here represents a used array slot. These diagonal lines of array slots can be thought of as geometric sums that both equal -1+2^6 = 63. Together the 2 lines approximately equal 2n. Remind yourself how in a binary tree, adding a new level to the tree will double the tree's size. Lastly, we have the n=64 array slots at the top of the graphic representing the final, sorted array we shall return. We use < 2n + n = 3n array slots throughout the entire algorithm. — E. Kaufman, Aug 19 '23 at 07:29

score 37 · Accepted Answer · edited Jan 28 '16 at 05:05

37

a) Yes - in a perfect world you'd have to do log n merges of size n, n/2, n/4 ... (or better said 1, 2, 3 ... n/4, n/2, n - they can't be parallelized), which gives O(n). It still is O(n log n). In not-so-perfect-world you don't have infinite number of processors and context-switching and synchronization offsets any potential gains.

b) Space complexity is always Ω(n) as you have to store the elements somewhere. Additional space complexity can be O(n) in an implementation using arrays and O(1) in linked list implementations. In practice implementations using lists need additional space for list pointers, so unless you already have the list in memory it shouldn't matter.

edit if you count stack frames, then it's O(n)+ O(log n) , so still O(n) in case of arrays. In case of lists it's O(log n) additional memory.

c) Lists only need some pointers changed during the merge process. That requires constant additional memory.

d) That's why in merge-sort complexity analysis people mention 'additional space requirement' or things like that. It's obvious that you have to store the elements somewhere, but it's always better to mention 'additional memory' to keep purists at bay.

edited Jan 28 '16 at 05:05

Kuai

135
7

answered Apr 27 '12 at 00:06

soulcheck

36,297
6
91
90

Do we need to even consider space already taken by input array or list into the equation ? Please see my (d)part. Also, why are you not considering the stack frame size that will be allocated on each recursive call. That would account for O(lg(n)) – Frank Q. Apr 27 '12 at 00:13
1

@FrankQ. from a purist point of view, yes. It's not necessary when can be inferred from context, but I wouldn't be surprised if someone gets his points cut on an exam for not mentioning it. True about stack frames, they're usually ommited, but can amount to quite a lot, it's still O(n) in array implementation though. – soulcheck Apr 27 '12 at 00:17
Could you explain how the size req by stack frames is O(log n)? At every level, no. of recursive calls is 2^j, so shouldn't the number of stack frames be 1 + 2 + 4 + .. + 2^((log n)+1)? I know I am missing something, can't figure it out. Similar is my doubt for extra array space. At level 0, we merge into array of size of n, at level 1 we merge two arrays of size n/2, so total allocation = 2*n/2 = n. So if we analyze this way, it should b n + n (log n times) = (n(log n)) What is the flaw in this analysis of mine? – Ayush Chaudhary Apr 21 '13 at 10:03
@AyushChaudhary in stack size analysis, you assume that merges will be taking place in parallel, while in reality you can only have O(log n) recursive calls stacked at a time. Also it's not the allocation count that counts (pun intended), it's the allocated memory size at a time. You can allocate/deallocate as much as you want but you'll never exceed O(n) additional memory allocated at a time. – soulcheck Apr 21 '13 at 10:24
1

@soulcheck By at at time, you mean in a particular recursive call? And since the same memory can be used later, we only look at the max size allocated at a time (i.e at the root of the recursion tree)? I couldn't understand the other part of the answer. There are O(logn) level but each level makes 2^(levelnumber) recursive calls right? root would need 1 stackframe, but since it makes a recursive call on EACH half, both the halves would require to store in the stack frame making the requirement 2^1 at level 1 and so on at last level, it would be 2^logn? – Ayush Chaudhary Apr 21 '13 at 10:59
1

@AyushChaudhary sorry, you're right. had to wrap my head around it again. It's still O(n) anyway. I'll correct the answer. – soulcheck Apr 21 '13 at 11:14
@soulcheck Well, now that I re read your last comment, you might be right. If it does not happen in parallel, but such that it first goes to logn levels in the left most branch, then deallocates for that node and then allocates for the next recursive call, then at a time there are only O(log n) at a time. Is that what you meant in that comment? Sorry about the confusion. – Ayush Chaudhary Apr 21 '13 at 11:21
@AyushChaudhary yes. I think it confused us both that OP wanted to parallelize the algorithm in point a. but not in point b. In case of parallel algo, you're completely right with your first analysis :) – soulcheck Apr 21 '13 at 11:24
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/28593/discussion-between-ayush-chaudhary-and-soulcheck) – Ayush Chaudhary Apr 21 '13 at 11:26

Vivek Korat · Answer 3 · 2020-10-13T04:49:32.390

Simple and smart thinking.

Total levels (L) = log2(N). At the last level number of nodes = N.

step 1 : let's assume for all levels (i) having nodes = x(i).

step 2 : so time complexity = x1 + x2 + x3 + x4 + .... + x(L-1) + N(for i = L);

step 3 : fact we know , x1,x2,x3,x4...,x(L-1) < N

step 4 : so let's consider x1=x2=x3=...=x(L-1)=N

step 5 : So time complexity = (N+N+N+..(L)times)

Time complexity = O(N*L); put L = log(N);

Time complexity = O(N*log(N))

We use the extra array while merging so,

Space complexity: O(N).

Hint: Big O(x) time means, x is the smallest time for which we can surely say with proof that it will never exceed x in average case

score 1 · Answer 4 · answered Apr 27 '12 at 00:01

1

a) Yes, of course, parallelizing merge sort can be very beneficial. It remains nlogn, but your constant should be significantly lower.

b) Space complexity with a linked list should be O(n), or more specifically O(n) + O(logn). Note that that's a +, not a *. Don't concern yourself with constants much when doing asymptotic analysis.

c) In asymptotic analysis, only the dominant term in the equation matters much, so the fact that we have a + and not a * makes it O(n). If we were duplicating the sublists all over, I believe that would be O(nlogn) space - but a smart linked-list-based merge sort can share regions of the lists.

answered Apr 27 '12 at 00:01

user1277476

2,871
12
10

For (b) space complexity with linked list is not O(n), you dont need extra space in merge procedure for sorting, you can move pointers around and perform in place merge? – Frank Q. Apr 27 '12 at 00:07
You have to store the n elements of the list _somewhere_. – user1277476 Apr 27 '12 at 00:30
Not necessarily when using linked list. – Frank Q. Apr 27 '12 at 00:51

score 1 · Answer 5 · answered Jul 19 '17 at 06:53

Worst-case performance of merge sort : O(n log n), Best-case performance of merge sort : O(n log n) typicaly, O(n) natural variant, Average performance of merge sort : O(n log n), Worst-case space complexity of merge sort : О(n) total, O(n) auxiliary

score 0 · Answer 6 · answered Aug 21 '19 at 13:34

0

for both best and worst case the complexity is O(nlog(n)) . though extra N size of array is needed in each step so space complexity is O(n+n) is O(2n) as we remove constant value for calculating complexity so it is O(n)

answered Aug 21 '19 at 13:34

fuad ashraful

1
1

score -1 · Answer 7 · answered Jul 18 '19 at 08:17

-1

merge sort space complexity is O(nlogn), this is quite obvious considering that it can go to at maximum of O(logn) recursions and for each recursion there is additional space of O(n) for storing the merged array that needs to be reassigned. For those who are saying O(n) please don't forget that it is O(n) for reach stack frame depth.

answered Jul 18 '19 at 08:17

Manjunath Bhadrannavar

147
1
5

2

Doesn't that merged array gets garbage collected after each recursive step? It should be O(n) space complexity and not O(nlogn) then – Kalyan Raghu Oct 15 '19 at 17:52

Merge sort time and space complexity

7 Answers7

Linked