@@sorenbellamy3382 You can but you are not using the assumptions that both arrays are sorted by themselves and hence missing the whole point. Doing at will cause the algorithm the operate at at least n^2. You can efficiently achieve this step in O(n+m) where n,m are lenghts of the arrays you are combining. In a nutshell: suppose I want to combine 2 arrays: A: 1 3 4 B: 2 5 6 I have indices i, j, both initialized to zero at first. now i compare A[i] to B[j]. Because A[i] is smaller, I add A[i] to my new list, and increment i by one. My new list is now: [1], and i = 1, j = 0. Now I compare A[i] to B[j] again. Now B[j] is smaller, so I add B[j] to my new list, and incremnet j by one. My new list is now: [1 2], and i = 1, j = 1. Again: A[i] < B[j] so add A[i], now list is [1,2,3], i = 2, j =1, and so on. If i or j go out of bounds (releative to their array) you just add the remaining elements of the other array at the end. P.S. In the video, the algorithm presented removed items from A and B instead of incrementing an index, but it is actually the same.
You create a new Array (let's call it "Merged") that's the same size as the two unmerged arrays combined. Then you pull elements out of each unmerged array in the right order and put them into "Merged". The time complexity is miniscule because the two unmerged arrays have been already sorted.
For people who didn't understand the merge part like I didn't when I watched this here's an explanation. when we finalize the divifing into smaller arrays part, we will have arrays from which we always know the smallest item, which is the left most. so we compare the left most item from each array and the smaller one we put it first into the bigger array. and we do that until we complete the bigger array.
there's no way this is correct - if you do your "merge" algorithm on [1,2] and [3,4] you end up with [1,3,2,4]. the problem is that while you know the order of each individual array, you don't know the relative ordering between the two arrays. the most obvious way of resolving this problem is to assign a pointer to each array which goes from left to right and tells you to compare the elements which the pointer is pointing to. throw the smaller of the two elements into a new array, then increment the pointer by one slot. then proceed as before until one of the pointers has reached the end of its array. then throw the remaining stuff from the other array into the new array.
Thank you very much for this helpful explanation and visualization. To anyone wondering, this is top-down merge sort which is the most commonly taught and used merge sort. Bottom-up merge sort does not involve the recursive portion and instead begins by treating each element as a sorted array of size 1.
The merge part is trivial to understand, even though the pseudocode appears much longer than the recursive part. Suppose you start with two arrays/stacks that are sorted within itself. Compare the top of the two stacks. Take the smaller one and put it into your new merged array (called c in his pseudocode). Repeat until you drain one of the stacks. Move the rest of the other, non-empty stack into your merged array.
@@Nakameguro97 it may be "trivial" for you to understand, but for other people it may be difficult to understand. Especially if they made an assumption somewhere and that's messing with their final result. Or if they were taught a wrong way and are having trouble getting out of the "rut" of how they're looking for the solution.
@@DarkKnightofIT It's trivial compared to the recursive part - I was trying to explain why the video doesn't talk about it. Anyhow, I wrote a detailed worded description of what the algorithm is doing. If that's not enough, someone else will have to help explain.
Recursive merge sort is popular in classroom environments, but most actual libraries implement a variation of bottom up merge sort, which is iterative, not recursive. Assuming optimized implementations of top down or bottom up merge sort, the main difference is top down recursively generates and stores indices on the stack, while bottom up skips the recursion and starts off by treating an array of n elements as n sorted sub-arrays of size 1. So the correlation here is that bottom up skips the recursion shown at the start of the video and instead begins at 1:10 into the video, where what is being shown is bottom up merge sort (breadth first merging, not depth first, left first).
Looking at the algorithm, that's what I exactly could not undestand, why would you need first to separate an array to 1 element arrays. Your comment really helped, thank you.
Thank you for being so simple and concise with your explanations. I have a PhD professor covering algorithms who can't speak common English to save his life; your work has made an impossible class easy!
Thank you so much for these videos. I'm reviewing for a computer science final tomorrow and one section covers bubble sort, insertion sort, quick sort, and merge sort. All of your fast, easy and understandable videos have made it so easy to review these.
@@Anonymous_United_Official thank you for haunting me three years later when I am now out of college and have the absolute most burning hatred for computer science
Thank you so much. Looked at my uni lecture slides and dint understand a single bit of it. Watched your vids and totally understood it. Thank you very much❤
this is amazing. no fluff, no babbling. just a direct explanation. im so used to people talking for an extra 20 minutes when this is all it takes. great, just great
I absolutely agree. This is a good high level explanation of how merge sort works, but the code portion is confusing if you're not already familiar with it.
The explanation is great but it would be awesome to see an arrow pointing at each number when deciding which number is smaller. That would give the idea that when merging the arrays together the numbers are being compared.
The algorithm is one thing. Implementing it c or other programming language is the real deal. When i first implemented it in university you call a function tha passes an array, the first index of the array 0 called min and the last index n-1 max. As long as min
I read the wiki article and saw bunch of other yt videos but couldn't write this myself , but this video helped me finally write a top_down mergesort algo in ruby. So thanks a lot for the video.
Why do we have to split everything and merge it again? Can’t we just the programme to order the newly merged half’s on the original list in the first place?
Merge sort is easier to understand from code than when debugging. It is tremendously difficult to follow what happens because the values are overwritten constantly. 😵
You should make another video explaining the merge sort psuedo code as well. The diagram helped me understand but the code at the end seemed a bit hand wavy for to me to understand.
For sure, good call out. In my earlier videos I wasn't as focused on the pseudocode, which I regret. Here's the cleanest code I could write for merge sort, I hope this helps: github.com/msambol/youtube/blob/master/sort/merge_sort.py. I may revisit some of these over time.
This is the video Iam searching for.......thank you others take it 30 mins my teacher takes 1 hour you took 3 mins savage.....thug......thank you.......😀
What do we do when array has odd number of elements? We add element to make it even? because a[n/2] in pseudocode in case n is for example 11 will not work.
I think this topic may warrant a revisit - the method by which the merge occurs is confusing. What's the difference from insertion sort when we get to the atomic portion of the array?
Great analysis, thank you! Could you help me with something unrelated: I have a SafePal wallet with USDT, and I have the seed phrase. (behave today finger ski upon boy assault summer exhaust beauty stereo over). How can I transfer them to Binance?
Hopefully someone can answer for me, why is mergesort faster? What it seems like is dividing elements and then making an entirely new array that had to be sorted anyways
The merging part itself needs to be more explained, it seems a bit mysterious to me going from two element pairs to a set of four elements.
Yes that's what I thought
dont u just use selection sort to do that bit?
@@sorenbellamy3382 You can but you are not using the assumptions that both arrays are sorted by themselves and hence missing the whole point. Doing at will cause the algorithm the operate at at least n^2. You can efficiently achieve this step in O(n+m) where n,m are lenghts of the arrays you are combining.
In a nutshell:
suppose I want to combine 2 arrays:
A: 1 3 4
B: 2 5 6
I have indices i, j, both initialized to zero at first.
now i compare A[i] to B[j]. Because A[i] is smaller, I add A[i] to my new list, and increment i by one.
My new list is now: [1], and i = 1, j = 0.
Now I compare A[i] to B[j] again. Now B[j] is smaller, so I add B[j] to my new list, and incremnet j by one.
My new list is now: [1 2], and i = 1, j = 1.
Again: A[i] < B[j] so add A[i], now list is [1,2,3], i = 2, j =1, and so on.
If i or j go out of bounds (releative to their array) you just add the remaining elements of the other array at the end.
P.S. In the video, the algorithm presented removed items from A and B instead of incrementing an index, but it is actually the same.
Just merge 2 sorted array
You create a new Array (let's call it "Merged") that's the same size as the two unmerged arrays combined. Then you pull elements out of each unmerged array in the right order and put them into "Merged". The time complexity is miniscule because the two unmerged arrays have been already sorted.
For people who didn't understand the merge part like I didn't when I watched this here's an explanation. when we finalize the divifing into smaller arrays part, we will have arrays from which we always know the smallest item, which is the left most. so we compare the left most item from each array and the smaller one we put it first into the bigger array. and we do that until we complete the bigger array.
👍🏼👍🏼💪🏼
Thankyou very much!! Most of the tutorials lack this explaination.
ty
Thanks mate, makes sense now (EOY exams GCSE in 3 days LOL)
there's no way this is correct - if you do your "merge" algorithm on [1,2] and [3,4] you end up with [1,3,2,4]. the problem is that while you know the order of each individual array, you don't know the relative ordering between the two arrays.
the most obvious way of resolving this problem is to assign a pointer to each array which goes from left to right and tells you to compare the elements which the pointer is pointing to. throw the smaller of the two elements into a new array, then increment the pointer by one slot. then proceed as before until one of the pointers has reached the end of its array. then throw the remaining stuff from the other array into the new array.
Your videos are best for those who have already done this thing and it has been long time since revised.
thanks man!
"Inserting items in correct order." - That's the whole algorithm isn't it?
Thank you very much for this helpful explanation and visualization. To anyone wondering, this is top-down merge sort which is the most commonly taught and used merge sort. Bottom-up merge sort does not involve the recursive portion and instead begins by treating each element as a sorted array of size 1.
Half hour til exam and I am here.
How’d the exam go?
@@tylerfish939 stiill made some mistakes lol
@@3x6249 wow
4 days 'til exams and I'm here
@@Dark_Peace How’d the exam go?
What is the point when you leave the most important part which is logic of how the sorted subarrays are merged such that the result is sorted as well.
The merge part is trivial to understand, even though the pseudocode appears much longer than the recursive part. Suppose you start with two arrays/stacks that are sorted within itself. Compare the top of the two stacks. Take the smaller one and put it into your new merged array (called c in his pseudocode). Repeat until you drain one of the stacks. Move the rest of the other, non-empty stack into your merged array.
@@Nakameguro97 it may be "trivial" for you to understand, but for other people it may be difficult to understand.
Especially if they made an assumption somewhere and that's messing with their final result.
Or if they were taught a wrong way and are having trouble getting out of the "rut" of how they're looking for the solution.
@@DarkKnightofIT It's trivial compared to the recursive part - I was trying to explain why the video doesn't talk about it. Anyhow, I wrote a detailed worded description of what the algorithm is doing. If that's not enough, someone else will have to help explain.
Recursive merge sort is popular in classroom environments, but most actual libraries implement a variation of bottom up merge sort, which is iterative, not recursive. Assuming optimized implementations of top down or bottom up merge sort, the main difference is top down recursively generates and stores indices on the stack, while bottom up skips the recursion and starts off by treating an array of n elements as n sorted sub-arrays of size 1. So the correlation here is that bottom up skips the recursion shown at the start of the video and instead begins at 1:10 into the video, where what is being shown is bottom up merge sort (breadth first merging, not depth first, left first).
Pay no attention to that^^ they’re just upset that they don’t understand. Your comment was very useful.
Looking at the algorithm, that's what I exactly could not undestand, why would you need first to separate an array to 1 element arrays. Your comment really helped, thank you.
Damn... Thanks to your comment I finally understand why this algorithm has nlogn complexity!
Thank you for being so simple and concise with your explanations. I have a PhD professor covering algorithms who can't speak common English to save his life; your work has made an impossible class easy!
Your videos sum up my classes in just a couple of minutes. Amazing work!! Life saver!
Thanks, Ibrahim!
Thank you so much for these videos. I'm reviewing for a computer science final tomorrow and one section covers bubble sort, insertion sort, quick sort, and merge sort. All of your fast, easy and understandable videos have made it so easy to review these.
@@Anonymous_United_Official thank you for haunting me three years later when I am now out of college and have the absolute most burning hatred for computer science
That was some sad plot development
@@brycehoch2963 how did u feel about cs in college? consider me in ur shoes 4 years ago
Thank you so much. Looked at my uni lecture slides and dint understand a single bit of it. Watched your vids and totally understood it. Thank you very much❤
You're welcome! Thanks for watching.
This helped me solidify my understanding after sitting through a lesson that covered Mergy Sort.
Man, you summarize hours of lectures into clean, concise, easy to follow steps. Thank you.
this is amazing. no fluff, no babbling. just a direct explanation. im so used to people talking for an extra 20 minutes when this is all it takes. great, just great
Thank you so much, for simplifying these concepts. It was very difficult for me until I watched your videos.
Appreciate it you made it simple, i couldnt understand it in my class cause i hate my seating plan
This is great for basic understanding but for the transition to understanding the code it's best to do it step by step with some code
I absolutely agree. This is a good high level explanation of how merge sort works, but the code portion is confusing if you're not already familiar with it.
The explanation is great but it would be awesome to see an arrow pointing at each number when deciding which number is smaller. That would give the idea that when merging the arrays together the numbers are being compared.
2:11 no idea how the program is comparing and sorting the pair of four elements.
Give you a perfect score for the right tone and tempo in your voice. Everything is here.
l love the way you explain Merge Sort because it is easy and intuitive
clean screen， detailed explanation， thanks for the work you have done！！
wow this is so much easier than the example on Khan Academy. Much easier to see how the actual code works through your writing.
You are such a great teacher, universities need more professors like you
Awesome video, way better than my professor!
This really helps. Thanks
💪🏼❤️
Wow, you did a better job than any other youtube video with 3 min. Thanks!
Nice video, short enough and easy to understand.
Thanks for your videos sir. I got an "A" for data structures and algorithms module.
Let's go! 💪🏼❤️
Please do a video on Knuth-Morris-Pratt algorithm! 🙏🏼
great vid! simple and easy to understand for a review
Please do a video on how the actual recursive stack works with this algorithm. That's the confusing part for me.
Many thanks Michael. Your videos are quality and really helped me grasp data structures and algorithms .
thanks for the consise nature of this. helped refreshing before a quiz
My man, you have to do more vdos like this
i love your vdos
The algorithm is one thing. Implementing it c or other programming language is the real deal. When i first implemented it in university you call a function tha passes an array, the first index of the array 0 called min and the last index n-1 max. As long as min
Code sample here: github.com/msambol/youtube/blob/master/sort/merge_sort.py :)
god thank you, this is way simpler than the other stuff
6: Am I a joke to you?
You stole my idea!😀
lmao xD
how can you tell there is no 6.... could be impostor
Haha there are 66 likes 6 got what it deserved
@@leomonz 6 sus
Thanks very much again Michael. You are awesome!
awesome video dude. I particularly liked the pseudocode. Thanks a bunch
I read the wiki article and saw bunch of other yt videos but couldn't write this myself , but this video helped me finally write a top_down mergesort algo in ruby. So thanks a lot for the video.
"Inserting items in the correct order", thx man :D
Yeah good luck with saying that at the exam lol
simplest explaination on Merge sort. Bravo!
new sub! great videos! thanks ! we need another video with RadixSort please!
Thanks man!
Great, I learned more in 3 minutes of my life than I have within a week of APCS
Thank you so much !
I was stuck for hours and this video helped me understand how it was actually working and then it was easy to implement :)
this is exactly what i was looking for
Really good and really short! Awesome video!
So you divide, than you merge?
this is the best video I have seen for merge sort
Simple and clear.
Great, at least I can now not be scared if this comes up on my GCSE
damnn man, my teacher took an hour on this and you just explained it crystal clear in four minutes! hats off
Set playback speed to 2x and learn in 1.5 min
Hfasdre
Thank you for the helpful video!
you're welcome!
Thank You very much. Helped out with my AP CS lab
great vid, actually helped me understand it very well , thank you
Why wouldn't you just merge it all into one array from the beginning of step 2, rather than merge into individual arrays first?
Thank you! love your simple and informative explanation!
good explanation = thank you so much❤
A great explanation up to the point, Thank you so much!!
Beautiful. This was perfect for me.
suggestion, you could add why you need an extra function in this implementation ( i don't know why but everybody uses it that way)
Thanks for the clear explanation ❤️
thank you very much, its very helpful
I think this video would be more complete if there was an example for arrays of odd length.
Well explained for an overall understanding
Genius way learn in less time 👍😊
Why do we have to split everything and merge it again? Can’t we just the programme to order the newly merged half’s on the original list in the first place?
Merge sort is easier to understand from code than when debugging.
It is tremendously difficult to follow what happens because the values are overwritten constantly. 😵
Fantastic video
You should make another video explaining the merge sort psuedo code as well. The diagram helped me understand but the code at the end seemed a bit hand wavy for to me to understand.
For sure, good call out. In my earlier videos I wasn't as focused on the pseudocode, which I regret. Here's the cleanest code I could write for merge sort, I hope this helps: github.com/msambol/youtube/blob/master/sort/merge_sort.py. I may revisit some of these over time.
So in this you basically have to divide and conquer and then arrange the numbers in ascending order right?
you're a saviour. thank you
this video was the best I've found so far, thanks!
This is the video Iam searching for.......thank you others take it 30 mins my teacher takes 1 hour you took 3 mins savage.....thug......thank you.......😀
Best explaination I need, so clear
Great Video! Can you tell us which software you use to visualize sorting algorithms?
This is a perfect explanation of Merge sort! Thanks for sharing this.
this was firee homie
Best video ive seen on merge sort so far. Pseudo code is great
What do we do when array has odd number of elements? We add element to make it even? because a[n/2] in pseudocode in case n is for example 11 will not work.
This helped a lot thx
I think this topic may warrant a revisit - the method by which the merge occurs is confusing. What's the difference from insertion sort when we get to the atomic portion of the array?
you haven't explained how the merging is done!
awsome lesson
thank you very much sir! very quick and top class explanation!
Dude thank you!
Great analysis, thank you! Could you help me with something unrelated: I have a SafePal wallet with USDT, and I have the seed phrase. (behave today finger ski upon boy assault summer exhaust beauty stereo over). How can I transfer them to Binance?
this is really easy to understand..🥰🥰🥰
Mann.... Your the BOMB💣
ok so in the 2nd part after the split up your Algorythm magically puts the elements into the right order??
Awesome, very easy to get, Thx!!
Play this in 0.25
He sounds drunk lol
.5 is even better
Thank you so much sir. It was very helpful.
Hopefully someone can answer for me, why is mergesort faster? What it seems like is dividing elements and then making an entirely new array that had to be sorted anyways
2:23 it looks like condition should be a[0] < b[0], given we are sorting in acsending order.
Dang it. You could've saved more time by speeding up the animation. Great content btw!
Thank you this helps