Four Semesters of Computer Science in 5 Hours Merge Sort

[00:00:00]
>> [MUSIC]

[00:00:04]
>> Brian: So we are returning to recursion land now. We're going to do our very first divide and conquer algorithm which is a merge sort. Now, insertion sort has been occasionally useful, bubble sort is never useful, merge sort is most often the one that you're probably going to use.

[00:00:24] So if you're doing like array.sort, 90% of the time, it's going to use merge sort underneath the hood, right? I say 90% because occasionally I believe it's Firefox's JavaScript engine will use quick sort depending on the data type. But for the most part, you can use a merge sort and the recently merged sort is mostly used is it's very consistent.

[00:00:48] It's very dependable what you can to get out of it. Yeah, a question.
>> Speaker 2: One question about the previous exercise. If you, from Drew, if you insert, doesn't it throw off the index?
>> Brian: If you insert, does it throw off the index? Yeah, it will, in fact, you can probably break out of it at that point.

[00:01:07] So again, we're not doing the micro-optimization at this point.
>> Brian: Yeah, I guess you could get some potential issues with that, it is throwing off the index and you could break out of the loop to kind of short circuit going through the rest of the array. So, it does throw off the index but at the same time you're taking something out and putting it back in so, it's just expanding the length of your sorted list.

[00:01:31] So, actually, would never be a problem because you would push out your largest element in that array and it would never be smaller than anything in the smaller part of the array. So, that actually ends up not being a problem, fortunately. [LAUGH] It could be a problem. Good question, Drew.

[00:01:50] I like where you're head's at, critical thinking. Okay, merge sort. Divide and conquer, meaning it's gonna use recursion, and when you hear recursion, I hope you're thinking it's gonna be log end something, log ends going to be throwing something into the big o, which you would be correct.

[00:02:10] It's very useful. It's used a lot of places. It's a stable sort. We'll talk about stable sorting here in a bit, and it's super consistent, whether it's sorted, unsorted, everything. It's all treated the same way, it all goes pretty much the same speed. And dependability, even if it's dependably a tiny bit slower, it's usually a good thing in computer science, because then you have a very known quantity.

[00:02:34] So again, if you having problem with recursion, like this gets a little bit tricky because the ceases recursion. Okay, so the basic gist of merge sort is you take a big list and you break it into two smaller lists, right? And then you're gonna take one of these lists and you're gonna break it into two smaller lists and you're gonna break it into, basically, until you're down to lists of one.

[00:02:59] At which point, you can no longer break it down any further and as we've talked about before a list of one is already sorted. So that's our base case. Our base case is we arrive at a list of one and then we're just going to return that sorted list of one and then, as we come back up, we're going to have a list of one in a list of one.

[00:03:19] And we're going to kind of stitch those together in a sorted way and then we're going to return that sorted list. So now, we have a list of two and a list of, maybe, two or one or something like that, and we're going to stitch those together in a merge.

[00:03:33] We call it merge, you can call it stitch. You can call whatever you want. I called stitch just to make sure that you get the difference that merge sort and merge are different. So I'm going to call it merge, sort, and stitch. But you'll see a lot people call it merge.

[00:03:46] And I'll talk about that stitching algorithm soon as I scroll down. Exactly after I scroll down. So you can do this in the same function. I recommend you split it out into merge, sort, and stitch or merge, sort, and merge. Whatever you want to call it, that's fine.

[00:04:03] But the basic gist is you have, let's look at this particular example right here. So you have, let's say that you're somewhere in the middle of your merge sort and you have two sort of list that come back to 1, 5, 6 and 2, 7, 8. One thing, because you know you're going to write an algorithm that's going to be turned sorted list to, you can, therefore, always assume that you're going to get a sorted list back.

[00:04:32] So this algorithm, the stitch algorithm can assume that it has two sort of list. Meaning, you don't have to provide for the cases of words unsorted right. Cuz if it gets to unsorted, that means something else is broken somewhere else. And we talked about this earlier that these algorithms are about making assumptions.

[00:04:48] As soon as we can make assumptions, we can do powerful things. So, because these two, I know, I'm positive, by the time it gets here, it has to be sorted, I can treat them like they're gonna be sorted. Meaning, I can use this algorithm that says that's only going to compare the top two things.

[00:05:05] So when you're first starting out, only zero elements get compared. So one and two, I'm gonna compare one and two and then I'm gonna say one is smaller sum, that's going to be the zero element for sure in the new list. So we're going to be creating a new list and we're going to be inserting these in a sorted way.

[00:05:26] So I'm going to take one and put it in the new list. So now I'm comparing two and five. I'm going to take 2, because 2's the smaller one. So now I'm gonna be comparing 5 and 7. I'm gonna take 5, cuz that's smaller and put it in the new list, okay?

[00:05:43] Compare 6 and 7, 6 is smaller so I'm gonna take that and put it into the new list. And now I've reached the end of this list. There's nothing left in that top list, sublist 1. So I can just assume, I can assume that I can add everything from the second list, just in order.

[00:06:00] So, list one has no more elements so I just go ahead and add everything from the second list on to there. Does that make sense? That's just the stitching part of the algorithm. The merge sort part of the algorithm is just breaking a big list into smaller list.

[00:06:18] That's it, that's pretty much all it does. It takes a big list based on the smaller list, calls merge sort on those and then it just says, okay, put list one and list two together. And hat's pretty much it. It's stable? So you have two elements that are equivalent.

[00:06:38] In this particular case, we're sorting numbers but you're not always sorting numbers. Say, you could be sorting, I don't know, people by last names. Well, some people have the same last name. But say you want to keep them in order that they were given to you in. So if I give you Holt, Brian and then I give you Holt, Nicky.

[00:07:00] Let's say I wanna keep both of those in order, so you don't want your algorithm to return to Holt, Nicky or Holt, Brian. You wanted to keep Holt, Brian, Holt, Nicky, so that would be a stable sort and some sorting algorithms like Quicksort, which we'll look at here in a second, is not stable.

[00:07:16] If they're considered equivalent, then they're gonna be jumbled and you don't know how they're gonna come back to you.
>> Brian: Now, you could argue, well, I want to be sorting my first name and last name. Well, you just have to make your sorting algorithm care about that. I'm saying, in the case that you're only sorting by the last name, just FYI if that wasn't clear.

[00:07:37] Okay, so merge sort is stable, which is another reason that the merge sort gets favored a lot of times is because stability is sometimes important, it's sometimes not right. Sometimes you don't actually care. Like, if one four comes back and in front of the other, you don't know nor care, right?

[00:07:54] A 4 is a 4 is a 4. So, in the case of sorting numbers, stable sort makes no difference. So again, tradeoffs. Algorithms are all about tradeoffs, and so stability is another thing you might wanna keep in mind when you're picking an algorithm. Okay, what is big O?

[00:08:13] Well, it's n log n. So we have to go over thing at everything at least once. In other words, when you're doing a sorting algorithm, you have to look at every element at least once. That's just a given, you can't sort things you don't actually know what they are.

[00:08:24] So you have to look at everything at least once, and that's why everything is gonna have at least n. There is no sorting algorithm faster than n. I promise, if you find it, you can make billions of dollars. It'll be like Silicon Valley. You'll do the middle outsourting or something like that.

[00:08:40] Okay, so then log in. So a lot of these other arrays take everything and compare everything to everything, right? And that's why you get n squared, because everything has to be compared against everything else. Because we're breaking lists down into smaller lists, not everything has to be compared to everything.

[00:08:57] That's why that stitching algorithms, because it's making assumptions that it's getting sorted lists, it can be slightly better than n, which is why we get log n. Spacial complexity is n, meaning, we're creating arrays and destroying arrays, which means we're getting a little bit less efficiency with memory which sometimes you care, sometimes you don't.

[00:09:20] For the most part, when you're in a browser and they have 8 gigs of RAM, you don't really care. So we don't care.