Four Semesters of Computer Science in 5 Hours Exercise 4 Solution

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

[00:00:03]
>> Brian Holt: Let's talk about merge sort. We're gonna do this in two functions. We're gonna do one and call it merge sort and then we'll call the stitch or merge, it's up to you. I have merge in my notes, but I'll actually probably call it stitch here just to be a bit clear that merge sort and merge are slightly different,

[00:00:21]
>> Brian Holt: Okay. So merge sort. We're actually going to break it down into two sort of, or into two lists right? So let's create our function const merge sort. Let's get rid of this too. Merge sort equals Nuns okay. The first thing we always do with recursion, recursive functions is base case.

[00:00:51] So if nums.length is less than two. Then, you're just gonna return nums, right because if it's a list of length one or zero. In this particular case will never see length zero but, if it's a length of one, then it's already sorted. So, we don't have to do anything about it, nor can we split it into any further.

[00:01:10] Right? And then here we're going to say const length, people's nums.length const.middle equals math.floor length divided by two and you can use ceiling, you can use round any one of those fine I simply chose floor. What floor does is basically says if you have If you give it 2.5 it gives you two.

[00:01:42] If you give it 2.8 it gives you 2. It just always rounds down for you. I like it cuz it's easy to communicate that like this is always going to take the smaller number. Okay, and then I'm gonna create two new arrays, left and right. You can call them smaller and greater.

[00:02:03] I choose left and right because that makes sense to me, it's the left part of the array, it's the right part of the array, what works for you.
>> Brian Holt: So const left = nums.slice 0, to the middle, and then const right equals nums.slice. Again slice is a JavaScript array function and this one is not destructive.

[00:02:33] Meaning, it does not actually modify the original array. And it's gonna go from middle.
>> Brian Holt: To, you can put whatever you want here is long as you get to the end of the array. I put length because length is always going to get you to the end of the array.

[00:02:50] I seem to recall that if you don't give it anything it will also just take everything but I'm quoting that off the top of my head. That might not be true. But definitely if you give it length that's always going to be greater than to the end of the array so that's a safe thing.

[00:03:06] Okay. So now, I have a left array and a right array that are equally split. I can guarantee that everything on the left array is everything that's not the right array and vice versa, right. Cuz the worst thing you could do is like duplicate, right cuz I need to be adding numbers to the array and I'll be bad, okay.

[00:03:28] And then here what I'm going to do is I'm going to call stitch.
>> Brian Holt: mergeSort left and mergeSort right. Okay? So that there's my recursive calls I call mergeSort on the left part and mergeSort on the right which is mergeSort is again going to break it down into smaller pieces, right.

[00:03:55] And stitch is when it comes back up the array as soon as mergeSort left returns. And mergeSort right returns is going to get fit into our stitching algorithm. If this is clear for you, you can also do const sorted left. = mergeSort(left) and const sortedRight = mergeSort(right). And then you can just call stitch on (sortedleft) and stitch on sortedright.

[00:04:31] If that makes more sense to you then my all means, do it like that. I'll just leave it like that because usually being verbose is helpful for readability. So.
>> Brian Holt: Okay. So that's it for merge sort, right? Now we're breaking all of our lists down into smaller and smaller lists.

[00:04:53] That we're then in turn going to stitch back together as we come up, right. So this is the first time that we. Usually, we were doing a recursion at the end, right. And just ending, right. Well, in this particular case, we're going to do our recursive call, actually, in the middle, right.

[00:05:07] And this is where preserving state in the middle becomes useful to us, right. So we're gonna do a recursive call on the left. A recursive call on the right. And then we're going to merge them back together. Okay? And we haven't written stitch yet but that's probably another thing that's worth mentioning about recursion is, it's kind of hard to wrap your mind around because I'm calling merge sort which I'm writing merge sort as I'm calling it So you just have to make this assumption that I'm gonna call mergeSort despite the fact that I haven't written it yet, right?

[00:05:40] And I'm just going to assume that at some future time, I'm going to make this crap work, right? So it's kind of a backwards way of thinking about. We're used to writing something and then using it, right? Instead of using it then writing. So, it's kind of a paragimre that you have to wrap your mind around.

[00:06:00] Okay, so any questions about that before I move on to the stitching part of it? There's nothing recursive about stitch, which is nice. All the recursion is done here in mergeSort. Great. Well, let's do stitch.
>> Brian Holt: Again, if you go to the answer part of this, it calls it merge.

[00:06:25] I just chose to call it stitch today because I was hoping that would make that a little bit clearer for you. I'm gonna call these left and right, however, it doesn't actually matter. You can call it right left, you can call array one or array two They have no meaning other than that they're just different.

[00:06:42] Right? So whatever works for you.
>> Brian Holt: Okay? So I'm gonna create a new array called results, right? This is going to be the one that I eventually return at the end, right? And then here I'm do a while loop. So while the left dot length and right dot length.

[00:07:09] So this is kind of a JavaScript trick. If you're not familiar with JavaScript. When left length of entry goes to zero because we're going to be destroying it as we go. You'll eventually go to zero right and zero when you coerce it right. So if I say if zero that also is equivalent to if false right So if it again, if it's easier for you if, length is less than or equal to zero right?

[00:07:39] That is essentially what I'm saying here, right? This is just a JavaScript shortcut way of doing it. So I'm saying as long as there's something left. In left and something left and right or if there's array still in the left and array items still in the right then continue doing this loop right.

[00:07:59]
>> Brian Holt: Okay and if you remember we're gonna just compare like is one smaller is two smaller and then we're going to advance one and not the other right that's kind of the algorithm part we're gonna be doing here. So if left zero,
>> Brian Holt: Is less than or equal to right zero,

[00:08:24]
>> Brian Holt: What we're going to do is we're going do results.push, right? We're actually gonna talk about stacks later today. The push basically says, take my element and tack it on to the end right. That's the basic gist of push. And then we're gonna do left.shift. Now a lot of people aren't super familiar with shift.

[00:08:48] What shift is, is just like there's a push and pop, there's shift and unshift. So shift is going to pop it off the front. Usually pop goes off the back right? So shift is going to take the first element or the zero element in left and it's going to take that off and it's going to push that into results right?

[00:09:08] So that's what's happening here.
>> Brian Holt: Okay, else as you might have guessed it's gonna be results.push right.shift. So again shift is something built into JavaScript arrays. Just as an FYI you can also do like results.unshift which is a terrible name right. So unshift is like push right so you're pushing on to the front right.

[00:09:42] That's what unshift does. So push and unshift pop and shift. I don't know why they went with that but it's the way it is. Okay so that's the first part right so that's as long as they both have something in them, right? And then we're going to run into the case and every single time That one of these arrays is going to have something left in it right and we have to put her and put all those on the end.

[00:10:15] So there's a couple ways to do this. I've chose to just keep using loops to hopefully be consistent. So while left at length results.push left.shift right. So it just looked like this right? You could also just do an array concat right? It would be totally fine to just do results.concat left right.

[00:10:44] That's still, in fact you can even do it like this. Pretty sure. Anyway, I'm not gonna do that. I just wanted to show you that we're doing the same thing. So I'm just doing the wild loops here. results.push right.shift. So whatever way works for you. This looks weird for someone because we're not gaining this by if statements but remember you're only going to have one of the arrays have something left.

[00:11:19] So if left runs out first then left.length is going to be zero. And it's just going to skip that array all together right? It's not going to do anything there or if right runs out first. It'll do left and then it'll just skip right. So that's why we're doing if lists left.length, right?

[00:11:35] Because we don't need to. It's unneeded. It'll never hit both of those, it only ever hit one of them.
>> Brian Holt: Okay. And then after that we just return results and that's it.
>> Brian Holt: Lets go change this to un x describe and it passes. So, any questions about Mercer, or stitch, or anything going on here.

[00:12:12] Does it make sense? Do we feel okay about like how that's working? It's kind of hard to conjure that magic out of thin air in your head like I get that like I'm giving you like twenty minutes to work on these and I had like two weeks of homework to work on this, right?

[00:12:26] So again this is the firehose like prepare yourself. But that's that's merge sort. That's what JavaScript for the most part is doing underneath the hood when you call sort. I think it's pretty powerful and cool that you now know that. Like you know how that works.
>> Speaker 2: Once you've done all those comparison and at the end the two wild loops, that's just, everything else at the end is pretty much already sorted, then you're just dropping it on the end of it.

[00:12:53]
>> Brian Holt: Precisely.
>> Speaker 2: Yeah.
>> Brian Holt: That's exactly what's happening.
>> Speaker 2: Okay.
>> Brian Holt: So to show you probably how I'd actually do this since this is kind of silly. You could do return results.concat left comma right cuz one of these is gonna be empty, right? And so it's doesn't matter if you add or you can do right left that's totally fine too.

[00:13:23] So you can just freely concatenate those on to the end and it's totally fine, or if you want to get even fancier because who doesn't you can do a dot dot dot results, dot dot dot left, dot dot dot right. And that actually works too. Mind blown, I see lots of perplexed faces.

[00:13:46] I use it later so let's talk about it. This is an ES6 feature, first of all, let's make sure I pass my test and I'm not just making, okay. Not making stuff up, I promise. This is called the spread, the spread operator.Yes this is the spread operator, cuz I get spread and rest operators cuz they look the same but they're in different places.

[00:14:05] This is the spread operator is saying I have an array result I want you to spread that out over this right? So in this particular case it's an array I'm saying take all of your elements and spread it over this new array. Then take all the elements of left spread that right.

[00:14:19] And actually if you can click view compiled up here in the top. And you can actually see what it's doing and this might be gross alone. Lets see if I can find it. Yeah so, this is including a lot of other stuff but down here. Yeah see it's actually just trans-piling into that which is kind of funny right?

[00:14:41] But that's what the spread operator does it's actually adding all these, it's spreading these elements over the array. And we'll use that later because I think it's kind of fun functionality to be a six. But again this is brand new, it doesn't actually work in every browser today.

[00:14:57] But it's coming etcetera etcetera, whatever. [LAUGH]