Analysis of Merge sort algorithm

See complete series on sorting algorithms here:
• Sorting Algorithms
This is part 2 of our lesson on Merge sort. Merge sort is a divide and conquer algorithm that has worst case time complexity of O(nlogn). In this lesson, we have analyzed the time and space complexity of merge sort algorithm.
See first part of this lesson here:
• Merge sort algorithm
Series on time complexity analysis:
• Time Complexity Analysis
For more such videos and updates, subscribe to our channel.
You may also like us on facebook:
/ mycodeschool

[@johnhurley8918]

I just noticed that when analysing time complexity, he color codes each operation by type: Teal = Simple actions Red = Loops Purple = Recursive calls That makes it so much easier to follow!

[@brentleylegend8964]

instablaster...

[@user-eq4oy6bk5p]

WAYWAYWAYWAY better than my prof's lecture

[@19.sairoopesh10]

The quality of these videos is amazing. The aspect ratio is perfect, the voice is clear, and I love how they use different colors for functions, recursion, and loops. It's crazy to think that this quality is from almost 10 years ago

[@macgyver985]

Best part, the videos are in the cinematic aspect ratio, so they look awesome on ultra wide monitors!

[@asmereg]

Wow, his is 2013 video. I'm watching it in 2020 to sit for my campus placements. Great explanation👏💕

[@7s3em]

absolutely amazing channel ! you are a GREAT teacher thank's alot keep up the hardwork

[@abhisheksharmacs]

this is the best that I have seen on Merge sort complexity

[@marcelluiz96]

Thank you so much! I needed to understand mergesort for a college activity, and this was the clearer and best explained method i've found :D

[@xitiz001]

Presented really well visually & orally. Great Work...!!!

[@calmyourmind5617]

The simple thing is : There will be logn levels to divide the array up to 1. and then for each level merge function is applied which itself takes 0(n) time. Therefore multiply n with the total step taken which is logn. The overall time complexity therefore boils down to 0(nlogn).

[@PeterXyzdlv]

Array of size 8, how many levels up to 1 ? 4>2>1 which is 3; log 8 base 2 is 3

[@dillon4321]

Best computer science videos on KZbin. Kudos to you sir

[@sashankaryal1223]

Such a wonderful explanation! Thank you so much.

[@pralakbhargav7113]

brilliant teaching!! I wish my Professors could teach like this!

[@mycodeschool]

Yes, We are reducing the expression at each step,, So, K is starting from 1 and increasing till we reach T(1) .. You can either reach me here or write to mycodeschool [AT] gmail [DOT] com

[@hovhadovah]

Incredible explanation, thank you so much!

[@ShreyaSingh-vr9qi]

One of the best video explaination of time as well as space complexity !!

[@alabimehzabinanisha]

Thanks a lot for being my Base Case of searching a Merge Sort Tutorial which will provide me details explanation. And of course, better than my Prof's lecture. :)

[@preetsingh239]

thanks for the awesome lectures ....please upload the rest of the lectures like heap sorting ,etc

[@kelvinluu7228]

this guy is actually a god. perfect way of explaining hard concepts

[@harshitanag2452]

Best explanation I found on youtube till date :)

[@selenewaide8994]

Great video, thank you for your clear explanation.

[@debarshiroy2939]

Your videos are so interesting, always forget to like. Thank you Sir for such clear explanation and hope for more videos

[@azukib2230]

Thank you! I needed a video to explain the formulas

[@jossba1628]

thank you for your help! I really enjoy watching your videos :)

[@simonetruglia]

This is better explenation about it than I never said, thanks a lot :)

[@RECOMMENDED_ACC_IMA]

Great way of explanation...loved it❤❤❤

[@bc8409]

thanks for giving us this. super helpful and clear. gj

[@youtubebaba1935]

Hey Man do you know how great work you are doing for others ? people like you makes the world beautiful :)

[@udaykadam5455]

Unfortunately he is dead.

[@ManojSaini_15]

Awesome explaination..i was just looking for an easy explaination..and you ended my search..;-)

[@usama57926]

bro you are an great mathematician

[@6304abhishek]

liked the space complexity explanation :)

[@elmehdifetouaki2641]

A fascinating explanation as expected, just as a remark, we could use master theorem and get the complexity easily

[@gajendragulgulia9889]

hey.. thanks for the great work. Will be good to have videos for Bucket Sort, Radix Sort and Searching Problems (Sequential Search, Binary Search etc)

[@CSshreyas]

excellent explanation, thanks for the video

[@ajayrajan8882]

My respects for #HumbleFool

[@AyushGupta-mm4jg]

He is not humblefool . He is animesh nayan

[@RAHUL-gf3ft]

@@AyushGupta-mm4jg he is Harsha Suryanarayana from IIIT Allahabad #humblefool

[@nileshgopale8528]

@@RAHUL-gf3ft he is Animesh Nayan , if you want to hear to audio of Harsha Suryanarayana , then access the Euclid's GCD Algorithm on mycodeschool.

[@navyasri5077]

@@RAHUL-gf3ft this iiitA people just💥🦸‍♀

[@RAHUL-gf3ft]

@@navyasri5077 Proud to be an IIITian

[@manishsen195]

Thanks a lot :) It is really helpful

[@jawadanwar6684]

You are the best, man

[@katarisaketh7222]

Thanks a lot man!

[@littleko93]

Great videos, thank you so much

[@zingzingzingbahh]

Thanks! this is perfect

[@bingqingwang850]

far more better than my teacher's lecture!

[@srinjoyghosh1467]

very nice explanation!!!

[@justinwmusic]

Translations: "into" = "times" or "multiplied by"; "by" = "divided by"; "upon" = "over" or "divided by"

[@vinutd210]

Thank you for the cultural translation. :)

[@ravi090191]

haha. Cool !

[@kautukraj]

Very helpful!

[@harshitasharma9061]

Wow!!!! Awesome explanation. Didn't knew about theta complexity. Everywhere I saw it was big Oh only. And many do not bother about space complexity. Thanks a lot. Please upload videos on heap sort also. Also sir if you could do some difficult time complexity questions on sorting algorithms, it will be very helpful for entrance exams (GATE etc.) Thank you sir!

[@shashanksahu1971]

This great programmer is not between us. fossiiita.github.io/humblefoolcup/humblefool/humblefool.html

[@taiebxr]

Here for space complexity and absolutely worth it alhamdulilah

[@Tracy_AC]

Good explanation.

[@naganikhilbijjala1000]

You are really awesome sir

[@ashuprakash6266]

I guess the Big-O notation is more famous ! Big O gives the worst case scenario that is the tightest upper bound. While Theta notation is for function bounded between two curves from down and above.

[@shashikantyadav4488]

nice video thanks very much.. its really helpfull

[@saidarahaasayyangalam3445]

I would have porbably joined for a course if you had provided..... No body can ever get these basics in such an interactive way you're providing us with...

[@mangeshrananavare5656]

Brilliant!

[@krishan7630]

Still You are the best Bro....Just watch your videos to revise topics :)

[@bolan167]

You are my hero.

[@tarunkr.9041]

PEOPLE WHO SO EVER HAVE DISLIKED YOUR VIDEO MUST BE UNIVERSITY PROFESSORS BCZ THEY MUST BE JEALOUS WITH YOUR TEACHING EFFICIENCY.

[@nooraalmarraj57]

thank you thank you thank you so much you are a life saver !

[@saurabhvemuri]

SIR PLEASE UPLOAD VIDEOS ON HASHTABLES

[@GIULI4994]

thank you thank you thank you!

[@arunrnambiar9561]

Why the memory consumed in stack not taken into account like in the space complexity analysis of fibonacci, exponential modulation etc

[@akhilsuresh2560]

TH BEST EXPLANATION ONE COULD EVER GET.. :) HaTS oFf

[@mycodeschool]

Hi Shanmuk, What is it that you do not understand? I can try explaining. Well, maths and programming go together. But, you don't always do such complex calculations to figure out time complexity. Recursion is tricky. I am sure you know enough maths to be able to program, that's why you are here. If you are not getting anything in this tutorial, ask specific questions.

[@senthilrajanr1]

I am having a hard time to follow the time complexity calculation. Maybe I don't know logarithmic and could be the reason. how come T(n/2) would become 2T(n/4)+c'(n/2). where does the c' come from? and i do not understand how 2^log2n T(1) will become nc. maybe it's just me but I could not follow. But thanks for doing this work. Appreciate it. If possible please try to do another video.Thanks

[@prabinlamsal5125]

thanks for the video.

[@xc0437]

Your videos are so good. Thanks a lot !!

[@adarozer]

Gülsüm hanım nasılsınız? Yedi yıl geçmiş aradan şuan ne iş yapıyorsunuz acaba :d

[@xc0437]

@@adarozer nostalji oldu yorumu görünce :p yazılım firmasında proje yönetimindeyim -.- siz niye düştünüz buralara matematikçilik mi var

[@adarozer]

@@xc0437 Yok ben vize için çalışırken bu videoya bakmıştım öğrenciyim daha bilgisayar mühendisliği okuyorum. İşinizde başarılar.

[@xc0437]

@@adarozer ne güzel sizin için başarılı okul ve iş hayatı dilerim

[@sunnyjain630]

what a nice way for teaching.. great man!! please upload count and radix sort algo thanks

[@shashanksahu1971]

This great programmer is not between us.fossiiita.github.io/humblefoolcup/humblefool/humblefool.html

[@mohitvarma1012]

@@shashanksahu1971 the narrator "Animesh Nayan" is alive and working at Google. His friend and co-founder Harsha died in car accident. Most of the videos are done by Animesh.

[@pravakarpatel3909]

Thanks for g8 explanation sir i got clear picture today on sorting .But i am confused when u said to clear extra memory but as these array is store in the static section it is deleted itself .sir Are u taking in case if it is store in heap section?

[@stormos25one]

great video

[@adityachendwankar1068]

awesome explanation.........!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

[@ShivamKendre-fc3su]

This person is awesome

[@AbhimanyuAryan]

mycodeschool at 9:13 are you using plug & chug method?

[@vishalm4074]

Can you give a link to logarithmic laws required to solve recursions ?

[@alrzhr]

well done

[@xuyuan4798]

Amazing

[@Bob-uk4bs]

the proof is amazing

[@excitedkiddo499]

amazing

[@mkab]

Thank you so much for this video. I have a question. I usually get confused when calculating the complexity of recursive functions. In this case why is it log n (I know that's the correct answer but why so)?. We have two for loops with complexity of O(n) which is greater than log n. Why don't we derive that the complexity of merge sort is simply O(n). Also since we are going to visit all the nodes in the tree, the complexity should be O(n) right? It'd be very helpful if you can explain this to me.

[@urvashidang6083]

It will be binary tree with two nodes always and height of binary tree is logn

[@usama57926]

hank for play lists

[@lakshaysharma8144]

can u plz make a video for greedy algorithms nd dynamic programming

[@Confusedalien1133]

this guy is dead

[@soundofprice]

what the fuck?

[@manaschakrabarti3924]

Yes that's true fossiiita.github.io/humblefoolcup/humblefool/humblefool.html

[@udaykadam5455]

It's sad as fuck ....

[@blacksplashmedia29]

Manas Chakrabarti wow smh

[@anuragreddy391]

Could you tell me the time complexity bcoz i am getting 0(n2) because comparing and moving is present

[@umairalvi7382]

Fabulous.

[@mohdfirdaus9050]

+mycodeschool hi, for the second step, I don't understand how'd you managed to get from c'n to 2c'n. Isn't it supposed to be c'n(1+1/2)?

[@atareen64]

we have to figure out the running time of two recursive calls on n/2 elements. Each of these two recursive calls takes twice of the running time of mergeSort on an (n/4) element subarray (because we have to halve n/2) plus cn/2 to merge, that's where you get the extra factor.

[@satyakibose8402]

Why is n/2^k = 1 at 9:29? And also, why at 10:06, 2^log2n = n?

[@panigrahisnehashish]

We can't determine T(n/2^k). But we need to get rid of T(n/2^k), and we know the T(1) = 1. Hence, we replaced with T(1). How T(1) is 1? Think up of a merge sort having 1 element will sorted in 1 unit of time. And, answering to your second question, log of n base 2 returns "x the POWER of 2 which equals to n". We are powering with the same number i.e. x (the POWER of 2) again, we'll get n. Try with some examples, you'll get it. ex: Base is 2. n = 8. Evaluation: 2 ^ log 8 = 2 ^ 3 = 8.

[@thoughtfulplatypus]

I'm not a programmer and I randomly watched this video and understood every single thing. So simple and clear.

[@ramannaagre7938]

can you please explain me what he taught

[@sreenag1255]

awesome

[@seanwalker2555]

ty so much

[@prasenjeetbiswal5275]

Hi, should not the space complexity be O(nlogn) ? When the left half is completely decomposed, it occupies "(n/2)*logn" space (logn steps) and the right half takes n/2 space. So total space is n/2*logn + n/2 which is equal to nlogn space.

[@PeterXyzdlv]

How ? Extra space required is just n; left subarray plus right subarray

[@chickenchowman2692]

Hi, what is n0 in your video?

[@apotessar88]

Sorry, I don't understand when calculating T(n) in 08:52 why T(n) = 2*T(n/2)+c'*n = 2{ 2*T(n/4)+c'*n/2 } + c'*n. Why we need to add c'*n in the end? and it also add c'*n in the following steps afterwards.

[@sandrok14]

+apo tessar Because it is recursive function. So for example on 8:52, on the second black stroke he has 4*T(n/4) from this he looked what was exactly T(n/4) equal to, so by the same formula he gets 2T(n/2/2) + cn, when plugs in n/2 to general formula. It is same as 2T(n/4) + cn. than he multiplyed by outer 2 which was there before and got 4T(n/4) + cn. The second cn comes from the same function for n/4 written recursively and other cn stays there as before so at last he added them and got 2cn. this get done K times so recursivley he gets kn. Maybe its bad explanation but its hard to explain by words ))

[@hangchen6131]

I still cannot understand it... like, if we expand 2{ 2*T(n/4)+c'*n/2 } + c'*n, it would be 2{T(n/2) + c'*n/2 } + c'*n = 2*T(n/2) + c'*n + c'*n = 2*T(n/2) + 2c'*n compared to original 2*T(n/2)+c'*n There seems to be an extra c'*n... Why...?

[@lowzyyy]

+Hang Chen what are you talking about? When you expand expression of course it wont be the same as original..because you are using T(n/4) to evalute instad of T(n/2) He is expanding the whole recursive formula to show you how to get idea of time complexity. Its easier to understand what is going on when u follow original formula..

[@vamshikrishna8143]

kzbin.info/www/bejne/nWKkqIiPltqknck

[@ARWA8400]

please can anyone explain to me what is n and from where we get it in O(nlogn) -space complexity "in case we do not clear extra memory" ?

[@TightyWhities94]

is this information really necessary outside of college?

[@akashraghav4405]

Yes! it is. If you're targeting to work at top organizations. you are expected to know how to analyze your code complexities and optimize if possible.

[@mayankmoolchandani7976]

thankYou

[@kumaratulith]

thank you so much....:)

[@phamvantho4981]

Best best best!!!

[@ManojSaini_15]

just had a small doubt if someone can explain (may be a dumb one..:/ ) When calculating T(n) array is divided into 2 parts so the k is incremented in every step. But I am confused with the calculation. How 2T becomes 4T and cn becomes 2cn.

[@rehmanarshad1848]

It's done recursively, basically just keep plugging in T(n/2) -> T(n).

[@sudeepkumar-pd9oq]

Imagine this great coder with great vision was not died in 2014, this was very unfortunate incidence for every code learner around the world

[@piyalsana1252]

what to return on the base case of mergesort function?

[@pratyushdas8267]

At 6:56 why is the complexity of Merge() C3.n + C4? Why is it not C3.n?

[@KarthickKani]

Thanks a lot :-).. highly recommended for begineers.. :-)

[@vandanagupta3408]

tooooooooo gud explaination...... :)

[@priyathammanu4741]

wat is the need to again calculate the time complexity ?

[@parthiban_k]

how to calculate the time complexity of creating left array and right-array

[@RohanB90]

Unfortunately none of the time complexity maths makes any sense to me. Having said that, the algorithm implementation was definitely a great help! Im hoping that just knowing that it is O(nlogn) time complexity if good enough

[@shahriarmim4696]

No not always. To be a computer scientist/engineer you have to know deep down of a code.