Transcript from the "Review: Merge Sort" Lesson
>> Bianca Gandolfo: So merge sort is a divide and conquer recursive sorting algorithm. So our divide and conquer steps our recognize the base case, we're gonna have divide, conquer and combine. So for merge sort our base case was when our array is a size of 1, right, we're just gonna return up because that's gonna be the sorted array of length 1, right?
[00:00:25] Our divide was every time we recurs we were breaking our problem into a left and a right. And our conquer and combine stops were the same. So when we were merging we were conquering, and we're also combining in one step.
>> Bianca Gandolfo: Cool?
>> Bianca Gandolfo: So here's just a big picture graphic of what all this means.
[00:00:51] So we have our unsorted list, and we keep breaking it in half, breaking in half until we get to our base case which is, every element is a sorted list of one, and then we merge them together in order. So we swap, merge these, merge these and then, again, we're gonna merge more, merge more until finally,
>> Bianca Gandolfo: We have it merged in order, yeah?
>> Bianca Gandolfo: Cool, so here is just some code for our merge routine, we have a while loop. So while our result is less than the left and the right,
>> Bianca Gandolfo: Lengths, you're gonna keep looping. So our left and our right again are, those are the two halves of the array in question that we're gonna merge into our result array.
>> Bianca Gandolfo: You would go through, push the one, that's smaller, and at the end you're gonna return it. So a couple of steps in there, but that's the gist.
>> Bianca Gandolfo: Cool?
>> Bianca Gandolfo: This is probably the toughest part of the merge sort algorithm is the merge routine.
>> Bianca Gandolfo: Awesome, so here is the entire thing, we have our base case, remember we have a list of one.
[00:02:33] So we're gonna divide it left, divide it right, we're gonna recursively sort the left, and we're gonna recursively sort the right. So what this does is we're gonna go left, left, left, all the way to the bottom. Then right, right, right, all the way when we get to the top, and then down the other way.
[00:02:51] And you're gonna return leftSorted and rightSorted and this is where we're merging them. So at the bottom, we're just merging one and one, and then as we recurse up it will be two two etc. And that way, cool, any questions about this?
>> Bianca Gandolfo: Cool, reflection, who here feels like, who here knew merge sort before taking this class?
[00:03:28] Okay, just David. Anyone else? Who here feels like if they were asked today in an interview they could implement merge sort? Maybe, maybe, okay. Where are the parts where you're like, my God, maybe I won't be able to do that part?
>> Speaker 2: Well, it kinda depends on, [LAUGH] like I could definitely pseudo-code it, I get it conceptually.
[00:03:54] But like the other night I tried to implement it just to make sure I still got it, and I ran into some, [LAUGH] just hiccups where it wasn't working exactly how I wanted to do it. But I think that's just kind of a practice thing I need to run through it a few more times.
>> Bianca Gandolfo: Cool.
>> Speaker 2: I think maybe the tricky part of merging is figuring out the logic of what to do when you run out of elements in one part.
>> Bianca Gandolfo: When the left or right is empty, is that what you mean?
>> Speaker 2: Yeah, so you've.
>> Bianca Gandolfo: Yeah, so like maybe the left array is a bunch of smaller elements and then you have your right array, which is a bunch of larger elements.
[00:04:38] As you are merging and looping through, suddenly your left array is empty and you have items in your right array. What do you do in that case? And that was something that was tricky for some people.
>> Bianca Gandolfo: Cool, what else?
>> Bianca Gandolfo: Anything?
>> Bianca Gandolfo: Any questions, about it?
>> Speaker 2: I never quite understood how it works when you have an odd number in the array and you're slicing it.
[00:05:17] Does that just round somehow and-
>> Bianca Gandolfo: Yeah, you either-
>> Speaker 2: So you don't have any control over what goes where?
>> Bianca Gandolfo: I mean, you can choose, right, you can round up or down.
>> Speaker 2: And in this example what are you doing?
>> Bianca Gandolfo: Let's see.
>> Bianca Gandolfo: So,
>> Bianca Gandolfo: Let's see, let's do array slice, let's make an array, and test out what happens.
[00:05:47] We want it to be an odd number, yeah? So we're saying array.slice and we're passing 0 and an array.length over 2.
>> Bianca Gandolfo: So this is gonna be our left.
>> Bianca Gandolfo: And then our right,
>> Bianca Gandolfo: Is just gonna do this, cool, so let's check it out. So our left, and our right so our right is gonna have the greater one.
>> Speaker 2: So is that built into slice that's doing the rounding? Cuz arr.length divided by two would return a decimal, right? This one's just an integer it drops the decimal in it?
>> Speaker 2: Did the division will, drop the decimal or the slice does?
>> Speaker 3: Slice does. Does it?
>> Speaker 2: Yeah, yeah cuz you're right.
>> Speaker 2: It would return 2.5.
>> Speaker 3: Yeah, but sliced as just treated as two.
>> Speaker 2: Cool, okay. Does Python do that?
>> Speaker 3: It's complicated.
>> Speaker 2: Okay.
>> Bianca Gandolfo: [LAUGH]
>> Speaker 2: Depends on whether you're using Python 2 or Python 3.
>> Speaker 3: Sure, okay.
>> Bianca Gandolfo: Cool, so that would be the difference if it was three.
>> Bianca Gandolfo: We would be missing something.
>> Bianca Gandolfo: Cool, good question.
>> Bianca Gandolfo: Thank you.
>> Bianca Gandolfo: Cool.