Merge sort time complexity

This video explains why merge sort is fast and time complexity is O(n log n)

[WebSurfingIsMyPastime]

best explanation ever. Makes the main point self evident

[lucaseastman]

I was struggling to understand why merge sort's time complexity was nlog(n) and you simplified this such that I could easily understand it. Thank you so much :D.

[techEnthusiastMw]

Best explanation I have gotten so far. Thanks

[kunal_chand]

Nice Intuition to why Merge Sort has O(N*logN) Complexity

[georgiot]

Great explanation. 1 issue though. You say that with merge sort "we keep on dividing the given input array into two sub arrays of equal size." Actually, they do not need to be of equal size and the given input array does not need to be evenly divisible by two. Just thought I'd mention this as most examples use an input array with its length being an even number but merge sort does in fact work with an input array with an odd length.

[sansritpaudel]

n(log2N) log of base 2 can't be ignored!!

[rickvianaldi]

Log n because
you see there are 3 level there,
log 8 = 3 (the number of level)

If the N is 16 then the level will be 4

log 16 is 4

[dangerpandaitslambda]

well explained! please upload more. Thanks

[Practice_dsa_together]

sir can u please tell like if thr r 8 elements merging happens 7 times so merge function which has a linear time complexity runs 7 imes but log 8 will give 3

[alans]

Thank you so much so easy to understand !

[sergio]

what about the initial operations where the array is divided until the sub-arrays are 1?

[rapidcodeswithgagan]

but height of tree is log n, where n is no. of nodes, but in our case n is the no. of elements in the array, n is not equal to no. of nodes

[tatscrochet]

thank u soo muchh, this is really helpful ^^

[flanker]

but when we call recursively each sub array get stored in a stack and gets called independently and not simultaneously(the other subarrays in the same level wait until the current gets executed) unless we are using multi thread.
So that makes the level count to 8 hence making it n^2 . Can someone please clarify this to me . Thanks

[chl]

So the time complexity of the example would be 8 * 3 = 24? I'm assuming height is 3, if we don't count the original input as part of the tree.