Merge Sort

[00:00:00]
>> Bianca Gandolfo: So the merge step, let's just look at this slide here. So during the merge step, we have two pointers which when we say two pointers, that means you're keeping track of some sort of index, right? When you were working with link list, you're doing a lot of things with two pointers.

[00:00:18]
Sometimes that means you have a nested loops, right, with indices being tracked. It also could be, you have some variable with an index, two variables with an index that's being tracked. So that's what, when people say, it's a common thing people say that just is kinda confusing. So we have two pointers, one looks at the beginning of this array, and one looks at the beginning of the other array.

[00:00:42]
And so, we ask at each step, which one is less. And so, in this case, three is less and we recreate a new array each time each of these steps, we're creating a new array. This is not an inplace sort and so, there is some memory, some space complexity things there to keep in mind.

[00:01:03]
So as we reason through this. So if 3 is less we push 3 on there, and so we slice it, this is gone. So now we're have 27 and we have 9, and we say, which is less? Okay, then we put 9. Okay, then that goes away and now we're still with 27 and we're looking at 10, 10 is less.

[00:01:24]
And then we keep going through that until we build up our final array and that's the merge step. So this is the conquer part of the divide and conquer algorithm. We're conquering it through this merge step. So what does that look like in code?
>> Bianca Gandolfo: Merge, left and right.

[00:01:48]
>> Bianca Gandolfo: Let's look at, let's try and think of the fastest way to do this. Let's just pseudocode it right together. Okay, so we went through the logic. Usually I would have you guys do this as an exercise, but we went through the logic of the merge routine. But let's pseudocode it out.

[00:02:14]
So we have a left list and we have a right list. So what was our example? So let's say it is 3, 27
>> Bianca Gandolfo: So, 3, 27, etc. And then our second list is going to be 9 and 10, [INAUDIBLE] a little bit shorter. So, 9 and 10.

[00:02:42]
So we're going to compare the first index of the left array,
>> Bianca Gandolfo: To the first index of the right array.
>> Bianca Gandolfo: Then, actually, the very first thing we want to do is initialize empty array. We initialize an empty array. And then, you want to push the lower value to the empty array, vabloo, value, to empty array.

[00:03:32]
And then you want to unshift or whatever. Shift, unshift?
>> Speaker 2: Unshift is [INAUDIBLE]
>> Bianca Gandolfo: What? We wanna remove the first one.
>> Speaker 2: Shift.
>> Bianca Gandolfo: Thank you. We want to shift the. Yeah, I always get them, cuz it seems like unshift sounds like you're taking something off. Shift the.

[00:04:01]
>> Speaker 2: Original array?
>> Bianca Gandolfo: Yeah, the array with the lower value. So you're going to remove that first one. Then you're going to repeat until both arrays are empty.
>> Speaker 2: In this case you'll be comparing 9 to 27?
>> Bianca Gandolfo: Mm-hm. So If we are going to look at it like this.

[00:04:30]
So we have our two arrays, we're gonna say is 3 less than 9? We can initialize our empty one here, we say yes. We add 3, we're going to shift that and then we are still keeping track. So we're gonna need to be incrementing the indices here. We're keeping track here, you can do that with a while loop.

[00:04:56]
And then we say, which one's less? 9, okay, we're gonna push 9 here and we're gonna shift that one. And then we find this one. And then, now this one is empty, so all we have left is 27. And so this one is empty, and then you would just return this sorted list.

[00:05:21]
And you're gonna keep doing that for each height. So you start with just two and then you go to four and then you're going to do the entire list. So that's the core. That's the meat of the merge sort algorithm, this merge routine. This is the divide part.

[00:05:45]
So you're gonna keep dividing it in half until you get a sorted list of one. So our base case is when array dot length equals one. So that's our base case. We're gonna start returning from that. And once we start returning, so after we return from our recursion, we are going to start doing our merge.

[00:06:13]
>> Bianca Gandolfo: So we go all the way down to our base case, and then we hit a return. My goodness. And then we return.
>> Bianca Gandolfo: And after, where we're returning our merge step each step of the way. Here is a visualization you can take a look at. There's also this really funny YouTube video, where they're doing Eastern European sorts, or they're dancing at Eastern European type Style to different sorts, that's kind of funny.

[00:06:51]
And there's lots of visualizations that you can take a look at. Okay, so here our base case is if list, that length is one or less than two. You're going to break the list in halves. You're gonna mergesort left, mergesort right. And then you're gonna merge the left sorted and the left right