Merge Sort

[00:00:00]
>> This is a recursive sort, this one's pretty difficult. I would say this is gonna be the first very challenging thing that I'm gonna have to do during the body of this course. So if this feels hard, it is hard, so I just want to give you permission before hand to be okay that this is gonna be hard.

[00:00:22]
All right, so let's apply a recursion to sorting a list. Kinda like insertion sort, where you assume that a list of 1 is already sorted. We're going to take that and we're going to apply that to sorting. So the idea here is that we have a list of length 10.

[00:00:44]
And we're going to take that and break that into two lists of length 5. And then break that again into things of two and three, and then eventually you're going to break everything down into lists lists of length one, right, using recursion. Once you arrive to a list of length one, that list is sorted.

[00:01:02]
That's the base case, right? So you return that list of length one, and then you're going to stitch together in a sorted fashion. The two lists that are coming back, right? So if I get a list of length one and a list of length one, those are two sorted lists and then I can write a merging function that's gonna take two sorted lists and stitch them together.

[00:01:26]
So let's see if I can kind of show you this a little bit. So let's say I called merge sort on this function here of 1,5, 7 ,4, 2, 3,6. Okay, I'm then going to call merge sort on 1,5,4,1,5,7,4 and 2,3,6. Okay, then I'm going to do this part first, right, because that's how the recursion is going to go, right?

[00:01:53]
It's going to go down one side and it's going to kind of go through the various different parts of the the tree. Okay, so I'm gonna take this list merge 1,5,7,4, that's gonna be broken down into merge sort of 1, 5, which also be broken down into this, but we'll do the first one first, then that's gonna be broken down into merge 1.

[00:02:12]
We're sort of 1 and merge sort of 5, so you can see here we're three levels deep in our recursion. Okay, so so far all we've been doing, we haven't been doing anything other than just breaking big arrays down into smaller arrays. Okay, so we hit here one is of length one, this is the base case, right?

[00:02:35]
So this level of recursion is just going to return back up so returns the sorted list of one. Okay, then it's going to call this one over here, merge sort of five. So, this is of length one, this is the base case, and it's going to return. So now we have merge sort on both of these from depth 3, they're gonna be returning back up to depth 2.

[00:03:00]
So now we're gonna call this merge function. Notice that merge sort and merge are slightly different. Merge sort, this is a recursive function, merge is not a recursive function. Merge is just a function then you're gonna write that you pass in two sorted lists. Now I'm extra emphasis on sorted, right, it has to be already sorted or all of our assumptions about this are gonna break down.

[00:03:29]
So what merge does is it just, again merges together two sorted lists will basically just iterate through both of those lists and say, all right is 1 or 5 smaller? Want a smaller, add it to the sorted lists, right? So, once the one of the arrays is empty, then you can just add everything on the right array.

[00:03:47]
So, in this case it's just 5, right, so, then we return back here. 1, 5 that's a new sorted list, right, that's what that merge algorithm does. It just takes two sorted lists makes one sorted list returns that. Okay, so now we have the sorted list of 1, 5.

[00:04:08]
Notice that that's actually originally what it was. But it doesn't know that until it's actually run the whole gambit of merge sort. Okay, so now it's going to pop back up to here because this part returned, right merge 1, 5, due to how recursion works, right? This is now finished, it's, returned back and it returned this 1,5, all right.

[00:04:35]
So now we're popping back up here to depth 2 and we're going to run merge sort on 7, 4. Okay, so that's going to get broken down again to merge seven and merge four. Sorry, merge sort 7 and merge sort 4, these are gonna be base case, base case there, and then those are gonna get returned back, and that's gonna merge, it's gonna get called on this list and this list, right?

[00:05:05]
So you're gonna ask the question, is 4 or 7 smaller, 4 smaller so you get this in the new array. Right arrays now empty, right, this one's now empty. So we can just blindly concatenate everything that's left in the left array. That's just one item, right, so now we have 4, 7, okay.

[00:05:25]
Now we return that back, that gets returned back up to here, right, this level. So now we're gonna call merge on these two lists, right, the, 1,5 which we got from up here. And the 4, 7 that we got here, again, very critical, these are both sorted and we know that, is 1 or 4 smaller?

[00:05:54]
1, you add 1, is 5 or 4 smaller, because we're just going down the list here, right? So we go to here and we're comparing 5 to 4, you say 4 is smaller, so we have 1, 4 here. Then you ask is 5 or 7 smaller, 5 is to get 1,4,5 and then left to raise now empty, which is, cause all that's left is 7, right?

[00:06:18]
And then you just add that to the race, so now we have a larger list of 1, 4, 5,7. Okay, and it's just this, right, all you're doing is breaking everything down to small problems and building them back up and you're building them back together by using merge, right?

[00:06:38]
I also see people call merge stitch, right, because you're stitching together two sorted arrays. So 2,3 ,6 that's gonna get broken down to 2 and 3 and 6, 2 and 3, 2 is base case 3 is base case. Then we're going to call merge 2 and 3, then out of that we get returns sorted array.

[00:07:00]
This should be 2,3, not 2,4, but yeah, 2,3 right there. Merge sort of 6, that's a base case, we return that, so now we're gonna merge together 2, 3, and 6, right? And by the end of that we get this return sorted array 2, 3, and 6, right?

[00:07:21]
So now we're back up to the point of here at the beginning, we have merge this and merge this, right. So that's what this is, and this is where we get our really big stitch together is 1 or 2 smaller 1 for 2 smaller 2 is 3, or 4 smaller 3.

[00:07:42]
And you can see together this gets stitched all the way until it is that the right away gets empty and we concatenate everything in the left array, and we end up with 1, 2, 3, 4, 5, 6, 7. So that was a long journey, thank you for sticking with me.

[00:08:02]
That is the entire algorithm, right, you have two functions you have merge sort and merge, the only thing that merge does is it takes two sorted lists and makes one sorted list. That's all merge does, it's totally blind to the rest of the world, doesn't care, not recursive.

[00:08:19]
It's just one simple function that takes two sorted lists and makes one sorted list. And then you got merge sort that all it does is it breaks big arrays down into smaller arrays and then it concatenates the things that come back from its merge sort recursive calls and passes those into merge.

[00:08:40]
So here's kind of a visual representation of it. And you might be asking, do I put does the left array have to be bigger than the right array, right? This one is a length 4, this is like 3, it doesn't matter, right? You can even be inconsistent, it doesn't matter.

[00:08:58]
Okay, so this breaks this down into eventually lists of length 1, and then it stitches them back together. Until eventually you end up back here with a sorted list.