Data Structures and Algorithms in JavaScript Pseudocoding Merge Sort

[00:00:00]
>> Bianca Gandolfo: So you see how that works? So this is the merge.
>> Bianca Gandolfo: This is divide. Dividing, conquering, that's the name of the game today.
>> Bianca Gandolfo: And it's recursive, see that?
>> Bianca Gandolfo: Cool.
>> Speaker 2: So instead of just sorting in place, you cut everything up and then you paste it back together?

[00:00:28]
>> Bianca Gandolfo: Yep.
>> Bianca Gandolfo: All right. We could look at a picture. You're can look at the YouTube video of this [LAUGH] of them doing some Eastern European dance.
>> Bianca Gandolfo: I won't force you to do it at this time.
>> Speaker 2: Really?
>> Bianca Gandolfo: What?
>> Speaker 2: Really?
>> Bianca Gandolfo: I'm really not gonna force you.

[00:00:51]
>> Speaker 3: But really, you have another dance visualization? [LAUGH]
>> Bianca Gandolfo: Yes, really.
>> Speaker 2: [LAUGH]
>> Bianca Gandolfo: Really, they have a dance for almost every major sorting algorithm [LAUGH] there is.
>> Speaker 2: [LAUGH]
>> Bianca Gandolfo: It's very awesome.
>> Speaker 2: That's awesome.
>> Bianca Gandolfo: Yeah.
>> Speaker 2: I'm gonna post that to my work [INAUDIBLE].
>> Bianca Gandolfo: You should, I was really happy when I've just found that one.

[00:01:08] It's ten years old,
>> Bianca Gandolfo: So I just happened upon it. All right, so here is our,
>> Bianca Gandolfo: Merge sort happening.
>> Bianca Gandolfo: Cool. All right. So here's pseudocode for the merge sort total. So we looked at the merge already. We wrote that separately.
>> Bianca Gandolfo: So here's the deal. So if the list is less than two, the length, return.

[00:01:51] That's our base case. Going to break into left and right. And then you're going to merge sort left. Merge sort right. And then you're going to pass it onto the merge routine.
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: So here's one that has a little bit more detail.
>> Bianca Gandolfo: So it's just saying that you're going to cut it in half.

[00:02:29] Left you're going to slice it. You're going to slice it. Pass it to the left. Pass it to the right. Merge left and right. I'm going to do the thing that I did with recursion yesterday. Remember that? Where I put it in a text editor. And we kind of talked about it.

[00:02:51]
>> Bianca Gandolfo: All right, let me make this very big. Is that good in the back size wise?
>> Bianca Gandolfo: Yeah? Tomar, is it good?
>> Tomar: It's good here. I don't know what what they'll see on screen.
>> Bianca Gandolfo: You can't see it either. Bigger? Good okay, here we go. All right, so here we are.

[00:03:19] Let's say that our array is, what was our array before? Like 34, 83, 10, 9. Five, that's four, whatever.
>> Bianca Gandolfo: Okay, cool. So here's our list. And I'm just going to walk you through what's happening, ok? So our base case, so we're going to call it
>> Bianca Gandolfo: So here's our first one on our stack.

[00:04:00] So this is going to be FALSE. We're going to break it into two-halves. What are our halves going to look like? Maybe it's going to look something like this. 34, 83, 10. That's going to be left. Right, 9, 1, and 4, yeah? We're going to pass left here,

[00:04:30]
>> Bianca Gandolfo: And then we just call it again. So here we go. This is us going deep, deep, deep.
>> Bianca Gandolfo: Nope.
>> Bianca Gandolfo: All right.
>> Bianca Gandolfo: So here's our list. We're going to break it up. Maybe we'll do it this way.
>> Bianca Gandolfo: So now this is left. This is right.

[00:05:18] We go here, we're passing our left, which is just 34,
>> Bianca Gandolfo: And I need to copy and paste this again, so here we go. Oops.
>> Bianca Gandolfo: All right.
>> Bianca Gandolfo: Are we following what's going on? Any questions? So we're just drilling down.
>> Speaker 2: Three would be true.
>> Bianca Gandolfo: See, you guys are watching.

[00:05:58] Did that on purpose just to trick you. [LAUGH] [SOUND] It's true, so we're going to return. So we're going to pop this off. Pop, it makes that sound actually internally. No, it doesn't. That would be awesome though if it did. And then we're going to go. Right? We popped off, we did that.

[00:06:23] Lsorted is now 34. We're good? Okay. So now we have 83 and 10, and we're going to go all the way, all the way down. And it's going to come back. It's going to come [INAUDIBLE]. I'm going to cheat so we can save us time. It's going to come back sorted.

[00:06:50]
>> Bianca Gandolfo: Right. Because return of the merge is going to be the merge routine of these two arrays. So we're going to put in 34,
>> Bianca Gandolfo: 34. And then we're also going to put in the 10 and the 83 as well.
>> Bianca Gandolfo: And what this whole merge thing returns is just one array that's 10, 34, 82.

[00:07:17]
>> Speaker 2: 83.
>> Bianca Gandolfo: 82. Thank you.
>> Bianca Gandolfo: And it also adds one, takes away one randomly. This is why the computer is going to do it and not me. Okay, so we're returning here. So this is the value that we're returning, this sorted thing here. So here's our return.

[00:07:48]
>> Bianca Gandolfo: And the arrow says that's what's being returned, so we pop this off.
>> Bianca Gandolfo: And now we're back here, and we're going to-. So LSorteds is now this, so I'm just going to erase this for us.
>> Bianca Gandolfo: Everyone following how that happened? Any questions about how that happened?

[00:08:11] Did you guys see what happened? Okay. So now we have right,
>> Bianca Gandolfo: And it's going to do the same thing all the way down to the right, and it's going to come back up. And this is going to be magically sorted.
>> Bianca Gandolfo: Then we're going to pass it in here, which then is going to merge them and return the sorted array.

[00:08:46]
>> Bianca Gandolfo: Okay, merge sort, we divided and we conquered two mountains. We dug deep to the end, down, down, down, so we only one sorted list of length one. We had multiple sorted lists of length one, then we came up. We merged them, merged them, merged them until we had one big sorted array.

[00:09:13]
>> Bianca Gandolfo: Seemed like a lot of work?
>> Speaker 3: Mm-hm.
>> Bianca Gandolfo: Surprisingly, it's not that much work,
>> Bianca Gandolfo: Compared to bubble sort or something like that.
>> Bianca Gandolfo: It's a lot of work for our brains, but for the computer, it's actually faster because the comparisons are much less. I might be getting ahead of myself.

[00:09:33] Are we good with how that all works? Question.
>> Speaker 5: I have a question.
>> Bianca Gandolfo: Sure.
>> Speaker 5: On the mergeSort, left and right says, but the return says just for [INAUDIBLE]. But we returned and the merges [INAUDIBLE].
>> Bianca Gandolfo: Yeah, yeah. So.
>> Speaker 5: Why do we say [INAUDIBLE] [CROSSTALK]
>> Bianca Gandolfo: What's happening in this merge sort, is that what you're asking?

[00:09:59]
>> Speaker 5: Yeah. That one word merge says is just merging, right?
>> Bianca Gandolfo: Yeah, it's merging them in the correct order. Just, it's sort of.
>> Speaker 5: The left and the right result.
>> Bianca Gandolfo: Yeah, so you pass the left and the right and then they are already sorted. But they're two different ones.

[00:10:17] So what the merge does is it makes it into one sorted array. Does that make sense? Yeah, we can talk about it more one on one when we do the exercise too.
>> Speaker 5: Just my question is the above is merge sort, that one is merged now so I now I understand.

[00:10:34]
>> Bianca Gandolfo: Okay, cool.