algorithm - Merge sort space and time complexity -

given 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 2 calls decide     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] , r[1...n2+1] new arrays    // idk , lets constant      i,j in l[],r[]         l[i] = a[p+i-1]         r[j] = a[q+j]  // shouldn't take time varying on size of array?                        // space too?      i=1 j =1           // constant time      k = p r     // below contribute 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 estimating o(nlogn) time complexity , keeping in mind there left , right arrays being created merged back?

and how come space complexity o(n) if size being used? won't 2 of them increased n, because filling array takes o(n) , l[] , r[] being created @ each recursion step.

i suggest reason drawing tree on paper: first write down whole array:

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

then write recursion causes 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 on each piece.

then, count how many rows you've written. close base 2 logarithm of number of elements started with (o(log n)).

now, how work being done each row? it's o(n). merging 2 arrays of lengths n1, n2 take o(n1 + n2), if have allocate space them (and don't in proper implementation). since each row in recursion tree has n array elements, follows work done each row o(n) , therefore entire algorithm o(n log n).

and how come space complexity o(n) if size being used? won't 2 of them increased n , because filling array takes o(n) , l[] , r[] being created @ each recursion step.

this more interesting. if indeed create new l, r arrays @ each recursion step, space complexity o(n log n). don't that. create 1 array of size n @ beginning (think of global variable), , store result of each merge it.

you pass around things identify subarrays, such sizes , indexes begin at. access them using original array , store result of merge in globally allocated array, resulting in o(n) space:

global_temp = array of size equal array you're sorting merge(a,p,q,r){      i=p      j =q              // constant time      while < q , j <= r // or similar condition                if a[i]<=a[j]             global_temp[k++] = a[i]             i++          else              global_temp[k++] = a[j]             j++      // todo: copy remaining elements global_temp      // todo: copy global_temp a[p..r]