I believe I have understood merge-sort to some extent and I was trying to understand the time complexity of merge-sort but find it hard to totally understand it. so we will recursively call mergesort to each(i.e. left and right sub-arrays), which will be log(n) and I understand that. but the merging part of the merge-sort says its complexity is o(n) making the whole time complexity, O(nlog(n)). but i don't quite understand how the merging part is linear becasue for every subarray call, there will be len(sub_array) * some constant operations. so if the length of the array to be sorted is n, then the merging part will be as ff according to my understanding: let k = number of primitive operations, n = length of sub-array, then total time complexity will be, here 2 is as there are two parts(left sub-array and right sub-array). 2(k)*2 + 2(k)*4+2(k)*8 + ......+2(k)n.(number of sums is logn times) but i don't know how is this generalized to nlogn?(like had it been k + k + k + k +.....+k n times, then it makes sense to say O(nk) and discard the constant k, however, in merge sort, it's not constant? so how is the time complexity really computed??
1 Answers
Let array length is n=2^k for simplicity. I'll show scheme for length 8 array.
At first we recursively divide array to 2^(k-1) chunks, then 2^(k-2) chunks and so on until length becomes 1
a b c d e f g h
Now we perform merging to size 2 chunks (ab denotes sorted array with a and b elements)
a b c d e f g h
\ / \ / \ / \ /
ab cd ef gh
We make 4*2 operations (not elementary operations, but every is O(1))
ab cd ef gh
\ / \ /
abcd efgh
We make 2*4 operations
abcd efgh
\ /
abcdefgh
And here we make 1*8 operations
We can see that we make log(n) steps, every steps takes the same number: n operations, so overall complexity is O(nlogn)
Related