Merge Sort Walkthrough

[00:00:00]
>> Bianca: So let's do our game with our pseudocode.
>> Bianca: All right, so let's say our list is, I don't know.
>> Bianca: Okay.
>> Bianca: So,
>> Bianca: We're gonna start with our list.
>> Bianca: So, is the list.length < 2? Nope, we're gonna break it in half. So now, we're calling mergeSort again on the left side.

[00:00:48]
>> Bianca: So,
>> Bianca: On the left side, which, if we cut it in half, we could just take these two,
>> Bianca: So you can do this. [7,6 and then 1,12]. So, remember, I said this was important for later. This is why it's important, because we are recursing on the left side, and then we're also recursing on the right side.

[00:01:25]
>> Bianca: So, we're gonna go all the way down to the bottom of our left side, so is it less than 2? 7,6, no, so we're going to do it again, where we're gonna break it,
>> Bianca: In half, it's gonna look like this. We're gonna have the 7, and then we're gonna have the 6, and we're gonna merge the left side, which is 7.

[00:01:52]
We're gonna put our little line here.
>> Bianca: Okay, I don't know where that 2 came from. Okay, so, is it less than 2? Yes, so this is when we return, so now we're returning a sorted list of length 1, which is 7, so this Lsorted is 7, okay?

[00:02:22]
We're good? So, we're popping this off, nothing else is executed, because we hit that return. Then, we're gonna go to the right sorted, and we're going to pause there. We're gonna pass in our 6,
>> Bianca: Pass in our 6 here, which we're just gonna return right away. We hit that base case, so we have our sorted list of length 1.

[00:03:00]
Now, we're gonna continue, and we're going to merge the left sorted and the right sorted. We talked about how the merge was gonna happen, but let's just skip that part, and understand that it's going to return these two lists merged in order. So, we have 6, and we have 7.

[00:03:19]
We good? We're gonna return this, we have a return statement, so we're gonna pop this off.
>> Bianca: And this is gonna be,
>> Bianca: Our left sorted list. Then, we're gonna continue on, and we're gonna do the same thing with the right side.
>> Bianca: And in the spirit of completeness, I'm gonna go all the way through this example.

[00:03:49]
So, the left side, what do we have, we have 1 and we have 12, 1 and then we have 12, all right? We don't have our base case, we're going to call the left side.
>> Bianca: Okay, so the left side is going to be 1, we're gonna return that up, because that is our sorted.

[00:04:14]
So, I just think this is genius, who thinks of this stuff, like assorted lists of length 1? Man, okay, so then, we're going to call it on the right side,
>> Bianca: And again, we're gonna do the same thing, we're just gonna return it, cuz we hit our base case.

[00:04:36]
Here we go, we get our sorted list of length 1, and then we're gonna merge it in this step, and we're gonna return that merged value. So, it's gonna actually just be the same as what it was. Cool, so we're gonna pop that off.
>> Bianca: And we're gonna reconvene where we left off., and now we're going to merge these two.

[00:05:03]
And again, we know that internally, this merge routine is going to pick it and put it in the right order. And so, it's gonna return [1, 6, 7, 12], and we pop that off, and then, that's our answer.
>> Bianca: Very short.
>> Bianca: Any questions?
>> Bianca: It's a fun one.

[00:05:45]
>> Bianca: All right, so I have some more pseudocode.
>> Bianca: And we can kinda talk about it like an algorithmic analysis, just,
>> Bianca: Very high level here. And we have some constant themes, like returning and cutting things in half, and then we have our merges, which is we're slicing it in half.

[00:06:13]
And then, our merge routine here, where we're looping through, the list is gonna be linear. And so, we can kind of imagine that to be, or is, in login time complexity for a mergeSort.