Merge sort algorithm
ฝัง
- เผยแพร่เมื่อ 1 ก.ค. 2013
- See complete series on sorting algorithms here:
• Sorting Algorithms
In this lesson, we have explained merge sort algorithm. Merge sort is a divide and conquer algorithm that has worst case time complexity of O(nlogn).
See source code of real implementation here -
gist.github.com/mycodeschool/...
For more such videos and updates, subscribe to our channel.
You may also like us on facebook:
/ mycodeschool
*4 years back when I was in college I studied for my exams from this video. 2 years later I watched this video for my placements. Now I'm switching my job and I already know where to go for Sorting lectures. Still the best!*
Great
Hi
Man we are on the same boat. Exactly the reason why I am here for the nth time. Mycodeschool is really my first and last school to excel.
Sorry for asking. I am a beginner .
is sorting that important that it takes these many years to master?
@@cpwithsundar When you'll start using Arrays.sort or other lib functions eventually you'll forget how these work
These videos are 7 year old , but still no body can touch the level of these videos. I watch so many tutorials but no-one provide such clarity. Bow down to you man. Really appreciate your work.
Yep. There won't be a need for any others. The thing about a lot of branches of mathematics - once certain algorithms / properties are discovered, they won't change. Not for hundreds and thousands of years. Occasionally we find more efficient ways to prove / achieve the same results.
One of the few accents of the world that I trust and feel safe with when it comes to learning CS
Indian accent 😐
Lol
Where are you from
@@schoudhury3463 I think India😉😄
LOLOLOLOL
I am studying this in April2021, still it's the best. No one can match this level, bahut bada change ho gya hota indians ka coding level agar Aaj bhi wo team work kr rhi hoti.. RIP Harsha,, u are immortal
The Lord Harsha
True brother I can't believe this playlist is actually 8 years old, still best on internet.
This video is legendary, it's like an archive of all CS students coming here to learn after professors can't explain it well. From comments made 6 years ago to 5 months ago, no one leaves confused
its low key sad but im grateful to those who make these videos
18 minutes of complete understanding vs 24 hours of breaking my head. Thank you so much!
Same here!
exactly
Pls explain me
What .
You're lucky guy. Me, it takes 3 days til watch this video and understand the whole thing
Your lecture meant a lot to me. I was on the verge of quitting college and computer science for good because I don't understand anything my professor taught. I was ashamed and full of self doubt and I often beat myself up because I struggled so hard to understand recursive and algorithm but making absolutely no progress at all until I found your video. Your teaching gave me hope and is the reason why I'm still hanging in there. You're an inspiration so pls don't stop what you're doing, I won't forget what you'd done. Thank You!
I've been through many videos of yours, and I can't stop telling my friends to come into your channel to watch. Your explaination is great. You explain the concept very well and, yeah, the visualization of each algorithm process is also easy to understand. :)
I watch these videos instead of my professor's online lectures
Lol same
Just came to know that one of the the co-founder of this channel Harsha passed away few years back, may he rest in peace. Your videos have been helpful ever since college to this point.
Any idea who are the other founders?
@@sohamhegde2386Don't remember but you can google that. Seems the channel is still running.
Out of the 3 techniques studied so far, this one, undoubtedly, stands the most elegant in all its form and execution. It's just beautiful to watch every little piece, in the end, fit itself in the right place automagically.
This is hands down the best explanation of Merge Sort. No other video breaks it down the way you did. Thank you so much!
Why youtube videos are greater and more helpful than school and university?
tnx a lot dude
Excellent videos! I have been trying to study for them for days and none of the other videos match the completeness of your videos..thank u so much for posting!
Thanks Natasha Gupta :)
My head was spinning when i tried to understand the merge sort by myself , thanks to your tutorial the logic of the algo is now pretty clear to me in a single instance.
All the best,Keep up the good work
Such a great job explaining this concept. This is the best walk through of the merge sort algorithm I have seen so far. Especially how you show the order in which the machine handles each step of the recursion process. Thanks for making this video!
Wow, 100% perfection & clarity. U R The Best Indian coder.
I was breaking my head for this merge sort and your explanation was perfect. Thank you Soo much. I watched twice and I implemented this on my own in JAVA the code is working great.
These videos had a significant impact on my algorithmic thinking. I'm grateful that I found these videos in first semester of college 7 years ago.
Thank for your great work, I have watched this long back and am still watching now to get refreshed on these topics. And your content gives that satisfaction of how nice it will be once you understand something. Thanks again.
Pseudo code was awesome clearly explained
i know a lot of people say that "hey you explain better than my professor", but for real merge sort was a nightmare since my class, but i could wrote the code myself with just your explanation. Thank you!
I just love the way you have explained the whole concept, Easy ,fast, understandable and most important easy to code
I always felt like the mergesort was daunting to implement so I never tried. And you have made it so easy to understand, cheers mate!
Thanks a lot for your clarification about Merge Sort!!! It is super helpful. I used to not understand because recursion is a struggle for me. But now, I can understand better.
I never comment on youtube, but this guy's explanation is phenomenal. Thank you sir
You have immense talent in simplifying things ! Keep up the great job. Thanks a TON !
My friend, i've been watching all kind of videos, about computer science, data structure, engeneering, etc, and I've never watched a so well-explained video this.
Never thought Merge sort was this easy. I was able to code Merge Sort algorithm myself after watching this video! Thank you, pal!
Brother ❤️❤️❤️Fan of Being techster❤️❤️❤️
Genius, you helped me get a 10 at A&DS, I apreciate your work!!
I keep coming to you videos every couple of years when I need them. Still the best!
What a high quality teaching!!! With this type of instructor, if you don't get an A in the class, you must really be dumb. Keep the good teaching. I wish some of my instructors could explain things with this details. Really cool following your tutorial.
Thanks a lot CseyCorpus
I think the main issue is that instructors like to teach very formally, but it should be done informally first. Then formally. This is how it should be taught. :)
I must be really dumb because I have never gotten an A in any of my courses at Uni. I am in my third year. 😂😂My best grade is A-...
your dumb for thinking that examination can determine a persons intelligence.
Yes I agree I am actually getting a clear understanding as well as gaining a new insight to recursion based on how you teach. You teach both from theoretical as well as programmatic (practical) and actually show what is going on in the stack which is really cool.
Can you teach the Minimax algorithm for applications to something simple like Tic Tac Toe ?
Well done! So hard to find folks that know technical subject matter well, while at the same time are able to communicate what they know well!
8 years on and this is still the only video I need to watch to understand merge sort. Thank you sir!
Great explanation, thorough and clear. You should consider teaching at university if you don't already! Better than most of my professors :p
what year do they teach this in university? Im learning this in grade 12 right now
I think freshman or sophomore?
Ryan Weiss what are some stuff you learned in freshman? thanks
Charles Z As a freshman they usually require you to take all beginner/common courses all various disciplines, then you start specializing your second year on when you declare a major and/or minor. First years of programming were basics of Java, how computers work, how programming works, all that stuff, very simple. Figure out what you want to learn, and then find a course that will be suitable. I taught myself most of what I know programming-wise early on, and didn't get much out of college, except some neat stuff like how to make your own languages, AI was kinda difficult, otherwise things we're fairly basic. Most of the stuff around CS when I was in college was a mix of theory and implementation, ie. sorting algorithms and graph traversals and all that kind of stuff, but they won't try to stick you with any specific technology, so they have to broaden their approaches to teaching, and for that reason it's tough to find a course that specialized skillsets can benefit from. Advanced CS courses can offer things like cryptography, AI, data mining, etc So just figure out what interests you, then how you can do it, and go for it. Lots to learn on the internet as well, but it's nice to be able to work it through with others if that's how you learn best. Best wishes.
what if I tell u the guy teaching died in 2014 at very young age.
You are making India proud.
+Mohmmad Ayaz Shaikh i understand nothing from this India...
Use closed captions on any youtube video you cant understand. Its the "CC" button in the bottom right corner of any video.
@Eos April Seriously? English is not even my mother language and I understand fine.
Eos April lol .. rip for uh then !! english lang. is not our mother lang. but still we indian can easily understand it either its american or UK english... nd uh people still remain as a dumb 😂
I now click on the programming videos from India first.
This is ridiculously the best explanation ever on the internet. I don't know if anyone who doesn't understands this will probably get an easier explanation anywhere. Thanks a lot dude. You explained the algo so well using pseudo code I could very well right my own code, in fact anyone should be able to.
Prior to watching your video I knew how to implement a merge sort and regurgitate the underlying logic, but I didn't really own the knowledge. The first 12 minutes of your tutorial connected the few missing links in my logic chain that a lecture and several hours of reading couldn't. Thank you very much!
The best explanation of merge sort recursion
U really need to consider becoming a prof if not already.
Amazing man!! Still watching in 2019!
This was a great tutorial. Very clearly presented. The subtitles while not needed is a nice touch. Awesome job!!
Fantastic! I was striving to understand that algorithm for a long time, now everything pretty is clear!
You have the ability to turn complex things into simple things!
Thank you for this bro! Explained perfectly!! Keep up on good work.
Thank you very much. Your explanation is very clear! You're awesome dude!
Its been 2021 but still cant find a better dsa series than mycodeschool !!
OHHH MY GOD THANK YOU SO MUCH. I was struggling trying to figure it out myself. Explaining how the commands are processed helped a ton.
Loved the way u explained
thanks a lot, you save my lab homework , I stuck on this hard algorithm :)!!
thank you very much.
Department of Computer Science, National Chiao Tung University ,Taiwan
same here
Same Here
Not in the same school obviously lol
woah .. im really amazed by this explanation of merge sort and the concept of recursion! one of the key things for me to keep on mind when thinkin abt recursions is for each level of recursion it goes into, think of the previous or upper level sublist/execution as “PAUSED”
and then when it returns/exit the recursion and merges (left+right), it continues back executing the upper sublist’s right half
Nicely articulated by breaking the algorithm down into sub-modules that helped make sense of the recursion. Thank you, this helped!
Thanku soooo much.. U explained better than any textbook could have :)
Thanks a lot Sara :)
It's really better than reading big reference books
Absolutely brilliantly explained! I cannot thank you enough. You should definitely do more Algorithm videos.
This is Gold. This content will never die till Algorithms exists in this world.
I have almost give up Computer Science / Programming. I was never a CS student, and I failed my first coding test when I was interviewing for a software engineering position. At that time, I didn't even know how a Linked List work.
I think it's around 3 years ago, I found this channel. The videos here inspired me what programming foundation is all about. I come back to this channel from time to time to clear my concepts on DS&A.
Today, I am a Data Scientist, and I am coming back again because I am having an interview from my dream company - one of the FANGs. I am sure that the content of this channel will help me to get through the interview.
I really want to pay tribute to myCodeSchool, because it just democratise the knowledge of Computer Science. It also inspires the world that, as long as you have a good teacher, you can learn anything you want.
Great🤍
mycodeschool is the best resource to visually understand DS algo. We are eagerly awaiting for more recent videos on new topics.
Really by far the best videos. Clear, understandable and complete! Thank you for your effort.
Sooo helpful. Thank you! :)
RIP humblefool ( Harsha Suryanarayana) Thank you for everything .
The tutor in the video is Animesh Nayan, Harsha's junior and Co-founder from MyCodeSchool.
Read more at: yourstory.com/2014/06/techie-tuesdays-humblefool
This is 9 year old video but it doesn't seem , the way he tell the concept so patiently and beautiful all doubt get eradicate and sense of understanding built with crystal clear logic .
I don't know how to thank you guys.........you cannot imagine how useful your videos are for college students....keep up the good work and I shall be much obliged if you could include lessons on heap,radix,shell sort and other sorting algorithms as well.......Thank you once again
u r a daddy programmer .excellent teaching skill .
I need a love react in TH-cam especially for this video!!!🖤🖤🖤
Thank you for such an amazing step by step explanation of the algorithm!!
Very useful in actually visualizing the whole recursion process!
Absolutely clear. I'll recommend this video to anyone looking to learn about merge sort. This makes it about as simple as it could be.
First of all, this lecture help me to understand how divide and conquer works, then how merge sort actually works and why the time complexity of merge sort is nlogn. Finally, it also help me to gain the basic knowledge of recursion. God bless you.
CS Student - Stony Brook University.
Hi Alam,
Glad that you found this lesson useful. Thanks for your wishes.
"One of the halves will have more elements than the other half" :D Anyway, great video!
I understood that video faster than this comment.
Does true half exist outside of theoretical math? Infinitesimal numbers would argue.
Videos uploaded in 2013. After 9 years still relevant. That's what quality content it. I wish you upload more videos on your channel
You're better than my professor. I exhausted my brain with my professor's teaching, now I am not worried anymore. Thank you!
/* C program for Merge Sort */
#include
#include
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i]
Hmm good
Dear #mycodeschool
These video lectures are simply amazing. Thank you so much. I just have a question, in your implementation how are you free-ing the memory allocated for left and right arrays using malloc?
Good catch vandana r ! The arrays should be freed. They are created using malloc, so they should be freed explicitly at end of the MergeSort function. Modified the code.
mycodeschool It this was written .NET framework you wouldn't have to worry about memory allocation and dealocation
yeah but also would cut ur market into a third
Brilliant and detailed explanation of the algorithm. This is the best one I've seen so far.
I have seen several MergeSort videos. This one is the best one to explain MergeSort algorithm.
Great Video... I only have one doubt how will we determine the length n of array A in function MergeSort() in real C code? i tried running int n=(sizeof(A)/sizeof(A[0])) but its not working inside MergeSort()..i think we will have to give size n as parameter to MergeSort()....
oh so sorry I didnt saw the github source code... many thanks for the source code...now i understood it's implementation clearly....
The explanation in CLRS is really very lousy. Thank heavens you made this video.
Great job explaining. You turned something complex into something anyone with basic programming skills could understand. Thanks!
@mycodeschool , Thank You Man, I understood the concept of Merge Sort really well for the first time.Awesome Tutorial , loved it
How can people dislike this video.....either they must be from some other planet or must be heavily drunk....
Thanks for the video. Have a question,
what will be the time complexity of merge sort for avg and best case? I think this is also O(n log n). Am i right?
Correct!
Siva k : Yeah, its O(nlogn) for all cases.
You're making my revision for a data structures & algorithms exam easy!
Bro this video is awesome, thank you so much. 9 years later i spent all my morning on the internet trying to understand this until I found you!
Your teaching efficiency is lg n, which I like very much. But our teacher’s teaching efficiency is 2^n...
nigga du u understand that higher efficiency is better.
@@SV-zi9os shut the fuck up moron
Benjamin Nitro you troll urself man 😂😂
Not all heroes wear capes...
Thank you so much! This was really helpful. This is the first topic I got to where reading the book alone wasn't enough. I really appreciate the tutorial, thanks
HANDS DOWN THE BEST CHANNEL FOR PROGRAMMING CONCEPTS!
take a bow sir !!
Thanks a lot Anurag :)
See source code of real implementation here:
gist.github.com/mycodeschool/9678029
Really useful video. Keep posting videos like this. I am just wondering how you make videos like this? What are the software used to create these drawings? Are you using any pen device to write with this precession or your control with mouse is just excellent? Thank you
Indrajith Indraprastham
They have a blog entry about this. blog.mycodeschool.com/2013/11/how-to-create-amycodeschool-style-video.html
mycodeschool
Thanks for the nice explanation.
In that
At line numbers 20 and 21 in the above code. (you mentioned in that link)
while(i < leftCount) A[k++] = L[i++];
while(j < rightCount) A[k++] = R[j++];
Instead of while loop, can we use "IF"? or is there any specific reason
for "WHILE"?. Because, after exiting the main while loop(line no. 16),
there should be 1 element left either in left array or right array.
For example, if the condition in mail while loop fails, the control
goes to 2nd or 3 rd while loop. In those loops, we are not checking any
conditions, simply putting the remaining elements in main array.Then why
we are using WHILE loop? I hope you understood what I'm saying or may
be I misunderstood the algorithm. Thanks!
i need source code without useing pointer
+Veerendra Kakumanu - no, it is not correct to think that (for all cases) only 1 element will remain in L or R arrays, after first while() loop exits. Consider this example of merging the following arrays: L = {1,2} and R = {3,4}.
Thank you! The last few minutes of the video were very helpful in helping me understand how a recursive algorithms flow. Thumbs up
I have never used merge sort before. But after having watched your video I could write the code for it myself. With a little glancing at your pseudo code. Fantastic explanation, I'll have to have a look at your other videos.
for average case we will use theta notation not the Big O notation.
chup kr ja bhai. pata hay nae kuch bakwass kr rha h theeta ka bacha
Ohh...tameez seekh le...gwaar...tb kuch seekhana..
hahah lodhuuu
@@amandeepsaxena9579
2019?
sorted -> 0 1 2 9
yes 2019.
Genius idea making these videos widescreen. Can't wait to see this on IMAX
I always used to mug up MergeSort and QuickSort. But thanks to you Sir, i am know able to understand every core concept of these algorithms. Thanks
I like when he says swapping. It's pronounced swopping.... not swapping xD but great video
this is not english class u idiot
It's pronounced swäp so he is right.
it's depends on your accent and what regional variations in the language.
papa ko pranam _/\_.,, arey!!!
pranam bhai:P
pranam beta
This channel was way ahead of its time!
I was pretty confused about the logic of merge sort until I stumbled upon your video, but now I am confused that why I was so confused about in the first place. The video is awesome. Thank you sir.
anybody in watching in 2018
even at 2118 also , this video (myCodeSchool) will stands outs of others