Transcript from the "Time Complexity for Merge Sort" Lesson
>> Bianca: Here is our analysis. We're just analyzing our pseudocode here. So all of this initializing and base cases, etc, that's gonna be constant. This kind of stuff really depends on the implementation. We don't really care. It can be a little more expensive, but it's not super important. The things that we wanna really take a look at is the merge left and right.
[00:00:25] So this is our n/2 operation. Whenever we're cutting something in half your mind should be like only got algorithmic. But then you're gonna pause because we have this thing called n*logn. Remember I was like, I'll tell you about n*logn. So merge sort is in log in because, yeah, we're cutting in half, cutting in half, but then we're merging it together.
[00:00:49] And remember we're talking about the time complexity of the merge being linear. So that's the N part and then the log in is the cutting in half part. And so we [SOUND] put it together and it's n*logn.
>> Bianca: Cool, are we good? So it would just be log in if we just cut it half, cut in half like the phone book, where we just rip it in half and we throw it away, rip it in half and throw it away.
[00:01:16] So we're ripping it in half and then we're like, my God, I need to stitch it back together. So that part that we could be saving us some time, we're like putting it back together. And so that's the N. Cool.
>> Speaker 2: Do we need to check whether they are even or odd?
[00:01:34] Like when you divide that by two?
>> Bianca: Yeah. Yea, yeah, so you're going to have to come up with whether, where you're gonna cut it, do some sort of rounding up. You know, math.max, or math.min, depending on how you wanna do it. Yeah?
>> Speaker 2: So why, with the other ones even when we combined methods you just took the worst case scenario.
[00:01:59] So why wouldn't we just call this one a.
>> Bianca: Yeah that's a good question, so the question is so before we just kind of said [SOUND] we'll just axe it, and this one we combine it. And that's because it's really let's see, that's a great question. So it really has to do with, how do I explain this like that.
>> Speaker 2: Is it because it's recursive?
>> Bianca: No.
>> Speaker 2: No?
>> Bianca: Maybe I don't have an answer to that question exactly. Yeah, does anyone know?
>> Bianca: Not even our math people know?
>> Bianca: Yeah.
>> Speaker 2: What's the question again?
>> Bianca: The question is why do we say this is n*logn and not just login when before we were just, we just chopped things off, why don't we just chop off n when we chop off-
>> Speaker 2: Well n*logn is, it's a constant multiple of n, right. So if you say, on, that could mean n or 2n or 5n or 100n, but the log n, logarithm grows very slowly but it grows to infinity.
>> Bianca: Mm-hm.
>> Bianca: Yeah, it's a math thing.
>> Speaker 3: Okay that makes sense, that makes sense.
>> Speaker 2: Yeah and there's been multiplying and adding that if you said n + login, of course, the login would be smaller and you could drop it. But it's because login is going to infinity you can't just throw it away.
>> Bianca: Yeah and it could have something to do with this equation.
>> Bianca: But, I can't be 100% sure, I'm not claiming to be a mathy person. But what I could tell you- Well, login is the number of times your splitting, right?
>> Speaker 2: The number of times you'll recurse.
>> Bianca: Mm-hm, mm-hm. And in is the merge, yeah. I can tell you that much for sure.
[00:04:07] The specifics in the math, totally over my head.
>> Speaker 2: That means when we split, the number of the splits most of it times our most, for instance here you have. Yeah [INAUDIBLE] when you do split, it is just almost three times like that. Log in comes from that [INAUDIBLE] Yeah, yeah, yeah.
>> Bianca: Yeah, I agree that the log in part is the levels, right? It's like the number of levels that come out of the splitting. And then the n is this part. And so when I'm thinking about the calculation, I think of the levels times the merge, which is linear.
[00:05:04] So that's how I think about it in my head, but I don't know if that's a mathematical fact.
>> Speaker 2: Remember that merge itself is a loop?
>> Bianca: Mm-hm.
>> Speaker 2: Right? So it's not linear [COUGH] it actually, I mean a double loop. It's not- No, merge is linear.
>> Bianca: Merger is a singular loop.
>> Bianca: So is n*logn [COUGH] is less [CROSSTALK] than n?
>> Speaker 2: It's more. N*logn is bigger.
>> Bianca: So let's take a look.
>> Speaker 2: If she says n*logn, I'm good with that.
>> Bianca: Right, n*logn grow slower, but you're doing n times log in. Log in grows very slowly, so think of a line with slope-
>> Speaker 2: We don't even have an end log in on this graph.
>> Bianca: So slope is increasing, but it increases slowly.
>> Speaker 2: Okay.
>> Bianca: Yeah.
>> Speaker 2: So it's similar
>> Bianca: Generally, so we put-
>> Speaker 2: Okay, cool. Are we good on the in-logging craziness?
>> Bianca: Mm-hm.
>> Speaker 2: [LAUGH] Yes we are.
>> Bianca: So the merge is the end. Splits is the log-in. That's all I got for you. Everything else is gonna require further research. We are going to go over the solution for recursive merge sorts. You're ready? How do we feel about merge sorts? Yeah?
>> Speaker 2: It exists.
>> Bianca: It exists.
[00:06:37] It's a cool thing. It's faster than any of the other sorts. It's pretty awesome. All right. Let's check out the code. So first thing's first. We have our base case, right? So if it's just an array with length one. We are going to return. Then we have our divide and conquer.
[00:07:00] So we're just slicing it in half. The left half and right half. And then we are recursing, first on the left and then on the right. And again, what this is doing, we're drilling deep first on the left, left, left, left. Then right, then right, right, right. Does that make sense to you?
[00:07:25] It's our little pyramid. And here's where the magic happens. So with mergeSort, the sorting happens on the combine step, hence mergeSort. It's gonna be different when we talk about quickSort in a second. So here we are, we're going to pass the leftSorted and the rightSorted. And that's gonna return up in here, remember, once we get to the bottom.
[00:07:50] And that's it, that's our mergeSort. I know it's like, man, that looks so much easier when the solution's up.
>> Speaker 2: So I think where we were running into trouble is within the merge, can you show the merge.
>> Bianca: Yeah, sure. Check on our merge. So here's our merge.
[00:08:09] We have your left and right that we're passing in and we're going to start off with your indexes, so we had those pointers. Remember we called them left and right pointer? Here we iLeft and iRight as well as our result array. So while the result.length is less than both of these.
>> Bianca: We're gonna keep going.
>> Speaker 2: That's what you are missing.
>> Bianca: Yeah, that's gonna stop you from going forever. So if our left pointer is basically, to the end of that array, we're going to concat our results. Opposite is true here. Here we go. This left, left at the pointer, right, that value is less than right at the right pointer.
[00:09:08] This is where we're pushing
>> Bianca: Otherwise, we are going to push the right.
>> Bianca: And at the end we return it. Cool.
>> Bianca: Sound good? You guys all have access to this in the solution branch as well. So the question came up before about n*logn and I couldn't find a definitive answer on the internet, but essentially what we're saying with n*logn is that so our merge is in, right?
[00:09:48] We have to merge with every recursive call, which is login. So we have to multiply them together and the question was, why don't we drop one of those digits. Why isn't it log in or why isn't it just n? And the answer is because we only drop significant digits and both of those are significant, right?
[00:10:09] So it's a little bit more than linear, right? It's linear times log in and it's less than a quadratic equation. And so both of them are significant. We multiply them because it's in the recursive loop. And that's why it's n*logn. There's a bunch of mathematical proofs you can go in and fool around with if you're into that.
[00:10:32] But in terms of estimating, that's how we estimate that. So,to answer you question about why we don't drop the n or drop the log in? Okay. Awesome.