Data Structures and Algorithms in JavaScript Pseudocoding the Merge Routine

Transcript from the "Pseudocoding the Merge Routine" Lesson

[00:00:00]
>> Bianca Gandolfo: So zoom in for a second. Continue zooming in. We're gonna do some pseudocode for the merge routine.
>> Speaker 2: All right, L and R the lists?
>> Bianca Gandolfo: Yeah, we have left and then we have right.
>> Bianca Gandolfo: So do you guys wanna do that with me or do you wanna do it on your own?

[00:00:19]
>> Speaker 2: Yes.
>> Bianca Gandolfo: Which one?
>> Speaker 2: [LAUGH]
>> Speaker 3: Can we do it with you?
>> Bianca Gandolfo: Sure. That just means I'm gonna ask you and you're gonna have to talk in front of everyone. So you have to be talkative. Do you guys commit?
>> Speaker 3: Yes.
>> Bianca Gandolfo: Can you put your, how does scouts honor work?

[00:00:36] Is it like this? Can we scout's honor? Or what's this one, this one's Star Trek? Okay, all right, great. So just to review, what is the merge routine again?
>> Bianca Gandolfo: We have two sorted lists. We go through each sorted list. We put the smallest one next and we keep moving around.

[00:01:00] Yeah, okay. Any questions about that? Does everyone got that in their head? Awesome, okay, great.
>> Bianca Gandolfo: So who wants to go first? What's the first thing that we need to do?
>> Speaker 2: Compare L

[0] to R

[0].
>> Bianca Gandolfo: Mm-hm.
>> Bianca Gandolfo: So if L

[0] is what?
>> Speaker 2: Greater than-
>> Bianca Gandolfo: Or less than, yeah.

[00:01:26] > R

[0].
>> Bianca Gandolfo: Wait, this is not pseudocode.
>> Speaker 2: [LAUGH] Pseudo pseudocode.
>> Bianca Gandolfo: Okay. Put 0 = R

[0].
>> Speaker 2: I'm assuming, do we have a second?
>> Bianca Gandolfo: Yeah, we can call it, you wanna call it output?
>> Speaker 2: Yeah, anything's really fine.
>> Bianca Gandolfo: Yeah, so-
>> Speaker 2: So then output 0 equals-

[00:01:59]
>> Bianca Gandolfo: So push lower number, which in this case is R [ 0 ], right?
>> Speaker 2: Yes.
>> Bianca Gandolfo: To,
>> Bianca Gandolfo: To output array, so seem fair? Mm-hm.
>> Speaker 2: And then push the other L's here.
>> Bianca Gandolfo: Else?
>> Speaker 2: Well.
>> Bianca Gandolfo: Else if?
>> Bianca Gandolfo: Elsa from Frozen? [LAUGH]
>> Speaker 2: It's not else, you want to do it any, so I guess within the if you could then do push L 0.

[00:02:43]
>> Speaker 3: Yeah.
>> Bianca Gandolfo: So, but what about for the case where- No, just what if the next one in R is smaller than L?
>> Speaker 2: It can't be, right? Or can it be?
>> Bianca Gandolfo: It could be.
>> Speaker 3: It absolutely could be. So you're always gonna have to compare back and forth.

[00:02:59]
>> Bianca Gandolfo: Cuz they're gonna be sorted a bunch of high numbers, then one could be sorted a bunch of low numbers. In which case you might have to take all the ones from the left first, and then all the ones from the right. Okay. It could be that way, you know?

[00:03:17]
>> Speaker 2: So yeah, sorry, go back to else.
>> Bianca Gandolfo: [LAUGH] [LAUGH] Let's see, let's try the back row.
>> Speaker 2: Us?
>> Bianca Gandolfo: Or [LAUGH] the middle rows. But, yeah, anyone, anyone.
>> Bianca Gandolfo: Okay, so we have an important step here that I will give to you. So we push the lower number which in this case (R(0) to the output array.

[00:03:54] We then need to move our pointer, right?
>> Speaker 2: Yeah.
>> Bianca Gandolfo: To the next one. So how do we do that?
>> Speaker 3: You move the pointer that you used.
>> Bianca Gandolfo: Mm-hm. So maybe we need to like have a pointer? Yeah.
>> Speaker 3: [LAUGH] Like have a pointer.
>> Bianca Gandolfo: Something like that?

[00:04:14]
>> Speaker 3: Yeah.
>> Bianca Gandolfo: So then this is gonna be Lpointer, right?
>> Speaker 3: Yeah.
>> Bianca Gandolfo: All right, now, come on. We can do this, look at that, beautiful, okay.
>> Bianca Gandolfo: All right.
>> Bianca Gandolfo: Okay.
>> [INAUDIBLE].
>> Bianca Gandolfo: And then our pointer. There we go. And then, so we just took,
>> Bianca Gandolfo: The first one, maybe.

[00:04:59] So we wanna increment our Rpointer, right? Yeah. Rpointer++, oops.
>> Bianca Gandolfo: So bad at pseudocode. Increment Rpointer, okay. Else.
>> Speaker 2: Just push the left one in increment.
>> Speaker 2: Else [CROSSTALK] push.
>> Bianca Gandolfo: Push what?
>> Speaker 2: I just to say Lpointer.
>> Bianca Gandolfo: L pointer, okay. Which in this case starting off as zero, right?

[00:05:51]
>> Bianca Gandolfo: So into the output array.
>> [INAUDIBLE].
>> Bianca Gandolfo: Yeah, probably need an output array.
>> Bianca Gandolfo: Some empty array, maybe.
>> Bianca Gandolfo: Great.
>> Bianca Gandolfo: So I'm just cleaning this up again.
>> Bianca Gandolfo: I'm just gonna call this RP. RP I like that.
>> Bianca Gandolfo: Okay, so we've pushed. So far we're like okay, is the right bigger or is the left?

[00:06:39] Okay, if the right is smaller, we're gonna put it onto our new one. Awesome, now we're saying, okay, our left one is smaller, we're gonna push that onto the next one, right?
>> Bianca Gandolfo: Great, and what's the next thing we have to do?
>> Speaker 2: Think you meant the left point.

[00:06:58]
>> Bianca Gandolfo: Great.
>> Speaker 2: Do you need to move?
>> Bianca Gandolfo: Move what?
>> Speaker 2: The R and the L based on where they took the number off.
>> Bianca Gandolfo: Yeah, so we incremented the pointers, but I think you're bringing us to our next point. [LAUGH]
>> Speaker 2: [LAUGH]
>> Bianca Gandolfo: [LAUGH]
>> Speaker 4: [LAUGH] I love that.

[00:07:25]
>> Speaker 3: I love puns.
>> Bianca Gandolfo: Our next point which is, okay, this is a procedure that runs once and then it's over. So we are [LAUGH] only gonna have array at maximum length 1 for our output.
>> Bianca Gandolfo: You know what I'm saying? Yeah, we have to loop.
>> Speaker 3: Mm-hm.

[00:07:49]
>> Speaker 3: Until we've gone through every number.
>> Bianca Gandolfo: Until when?
>> [INAUDIBLE].
>> Bianca Gandolfo: Yeah, until L and R.l or something. Yeah.
>> Speaker 3: Yeah.
>> Bianca Gandolfo: It's equal to, LPR or something to that effect.
>> Bianca Gandolfo: Okay, so let's walk through this. So we have our two arrays, we are initializing two pointers, we have our left pointer and our right pointer starting at zero, right?

[00:08:39] We have an output array, empty. That's gonna be our answer. We're gonna loop, as long as both our left pointer and our right pointer are less than the length of the left and right arrays minus one, or whatever. We're gonna keep running this if else statement. Yeah? Great, so let's indent that properly so that's really clear.

[00:09:12]
>> Bianca Gandolfo: So if,
>> Bianca Gandolfo: Left is greater than right. We're gonna add the right. Otherwise, we're gonna push the left one. Yeah? Cool. So this is the basic logic around here. There's a few bugs, like what if it's undefined? Stuff like that. But, for the most part this is the merge logic.

[00:09:42] Any questions about this? This is just one part of the merge sort. Does anyone see any major blaring errors?
>> Speaker 2: Well, when you get to the point where one or left or right is empty.
>> Bianca Gandolfo: Mm-hm.
>> Speaker 2: That's what you're talking about, is a bug that we can work out later?

[00:10:00]
>> Bianca Gandolfo: Yeah, yeah, so you have to account for that.
>> Speaker 2: Yeah.
>> Bianca Gandolfo: It should only be like,
>> Bianca Gandolfo: Well, I don't know, I'll let you figure it out. I don't wanna give you too much. Okay.
>> Speaker 2: [LAUGH]
>> Bianca Gandolfo: Cool?
>> Bianca Gandolfo: And then you're gonna return your output right after.

[00:10:24]
>> Bianca Gandolfo: I think this is solid. A couple bugs in there, but the logic flows in line with my understanding of how the merge routine works. Does anyone have a different idea of how the merger team should work? There's some conflicting brain stuff happening, no? We're swapping place instead of pushing, but that's quite more complicated.

[00:10:53]
>> Speaker 5: Well in this case we can't really swap in place, in this particular case, because we're just doing a snippet. But it's possible.
>> Bianca Gandolfo: But not right now. But yeah, good thought. Okay, anything else?
>> Bianca Gandolfo: Okay, all right. So that's the merge routine. That's the combine and the work, cuz the merge is sorting and it's combining.

[00:11:29] Awesome. Two for one. So here's a picture for us. So when we're going through the divide part, we're gonna divide doot, doot, doot all the way down. This my each doot. Doot, doot, doot, doot. You see that. So we cut it in half. And then we cut it in half until we get to a length of one.

[00:11:54] PS that's your base case, hint, hint. Then once we get to our arrays of 1, those are all sorted, right? When you have an array of 1 element, sorted, awesome. Then we merge. We say, which one is less? We'll put it, just like the merge routine. So this is the merge routine for 1.

[00:12:17] This is the merge routine for when the length is 2. Merge, merge, merge. And this is the one that we did as an example.