This course has been updated into a 4 part series! We now recommend you take the A Practical Guide to Algorithms with JavaScript course.
Transcript from the "Merge Sort" Lesson
[00:00:00]
>> Bianca: Merge sort, which is our first sorting algorithm. That is sub-quadratic time, which is great. Just means that this is a sorting algorithm that can take a substantial amount of data and sort it for us, so it's pretty exciting. All right, so divide and conquer. So divide and conquer, when you think of divide and conquer the first thing you should think of is recursion.
[00:00:28]
>> Bianca: Yeah? Who here has done divide and conquer some time? Okay, cool. All it means is, you take a problem, you break it into smaller sub problems. Do the work on each sub-problem, and then maybe combine them together. The next divide and conquer, where there's no combination step, but this is the general recipe, is that there is some combination step at the end.
[00:00:52] And for us, merge-sort, you might guess that the combination is a merge at the end, maybe. Cool? Yeah, and you have to recognize a base case, so you don't have an infinite loop. Great.
>> Bianca: Here we are. So I'm just gonna show you the merge routine first, before we break down the entire merge sort.
[00:01:21] So we start with these two sorted lists, and we merge them into one sorted list. The way we do that is, we compare the first one in this sorted list with this one
>> Bianca: If this one's smaller.
>> Bianca: We put it in there, we put it in the final one.
[00:01:49] Then we compare the next one with the next one, and then we put the smaller one.
>> Bianca: Again compare, compare, 10's gonna be smaller. We are going to x it. 10, 27, 82. 27 is smaller.
>> Bianca: All right, so we compare 38 to 82. 38 is gonna to be smaller, although my dyslexia almost made me say the other one.
[00:02:25]
>> Bianca: All right, we have 43, 82. 43 is going to be smaller. Pop it in there. Don't forget our x, and then we have 82. So that's the procedure of the merge routine, right? We take these sorted lists, and because they're sorted, we can do this much easier.
[00:02:46] Can someone guess what the time complexity of this might be.
>> Bianca: For this routine?
>> Speaker 2: I'd say it's going to be equal to whatever the shorter of the list, cuz you have to do a comparison equals length of the shorter list, right?
>> Speaker 3: Don't you think [CROSSTALK] linear?
[00:03:12]
>> Speaker 2: Merge is linear.
>> Speaker 4: It's exponenential, log?
>> Bianca: I have heard every single one.
>> Speaker 2: I know.
>> Bianca: This is great.
>> Speaker 2: That's gonna throw out in a sec.
>> Speaker 4: It's maybe exponential?
>> Bianca: Exponential?
>> Speaker 4: Yeah.
>> Bianca: Well, the thing about merge sort that we know, is that it's not exponential for sure.
[00:03:28] Cuz I said at the beginning, since it's divide and conquer it's not gonna be exponential. So there's not gonna be nested loops here. So given that, cuz a few people said exponential, maybe cuz we're just thinking, my gosh, we have to do all these comparisons. Maybe it's gonna be like a nested loop, cuz that's what we've been doing.
[00:03:48] But actually, if you think about it, we just have a pointer, and we're just incrementing pointers on over one list and pushing it into another list.
>> Bianca: So you're just comparing. You don't need to do a nested loop.
>> Bianca: That make sense? Cuz you're not comparing all of these to all of these, you're just comparing the first ones, or the second, as you pop them off.
[00:04:17]
>> Speaker 2: So you're saying it's linear?
>> Bianca: Mm-hm, yep.
>> Speaker 2: But if you had a list of 100 that were sorted and a list of 20 that were sorted, it would only be 20 comparisons, right? Cuz I need to take the rest, the remaining-
>> Bianca: Yeah, it sort of depends on how you implement it, but yeah, hopefully you have an optimization where that will just copy the rest of it over, and it will still be linear.
[00:04:44] Because you'd still have to copy each one over, you know what I mean? There's no bulk copy paste situation, unfortunately. But the way it works is, we divide and conquer, and you roughly divide it in half every time. If it's an odd number, it kinda gets. It might be one off, but for the most part, it's not gonna be 20/80.
[00:05:08] And for the most part, I mean, never. If your implementation's doing that, then that's something, that's not a merge sort.
>> Speaker 4: What if the two lists are not sorted?
>> Bianca: If they're not sorted?
>> Speaker 4: Yeah, at the beginning
>> Bianca: Then it would be quadratic, if it wasn't sorted.
[00:05:26] But that's the magic of the merge sort, is that we know that each of these smaller arrays are gonna be sorted, because we are gonna do that ourselves. We're gonna do that work. Yeah, but I just wanted to sort of zoom in here. We zoomed in to the merged part, and then we're gonna zoom out.
[00:05:41] We have, in this divide & conquer, the base case, breaking down the problem, doing the work, which in this case is the same as combing it, because our work is sorting it. And merging is where the sorting is really happening. And we'll see what that means in a second.