Merge Sort Practice

[00:00:00]
>> What is the big O here? The nice thing about Merce sword is every case is the worst case scenario. Every case is the best case scenario. Every case is the average case scenario. There's no difference between the best and the worst case of merge sort, right? Imagine if this was just 1, 2, 3, 4, 5, 6, 7, right?

[00:00:24]
This still would just get broken down into seven arrays and then stitched back together. It actually makes zero difference to merge sort. If it's reverse sorted, sorted, shuffled all those things you end up with the exact same algorithm. So that's goodness, right? That's good news. That's why most JavaScript engines like spider monkey v8.

[00:00:49]
JavaScript core, most of them use merge sort under the hood. So if you call .sort or they're probably calling merge sort. They might be calling quicksort sometimes. We're about to do quick sorts so don't worry about that. So that's the good thing about merge sort is like, it's just a solid.

[00:01:11]
If you don't know what's coming in Mercer is always a safe bet that like this is going to be pretty performant. So, let's talk about the big O of what it is then. Does every number get compared to every other number in the array? No it doesn't. Because we're using the fact that, if you have one sorted array, and you have another sorted array.

[00:01:45]
If 1 is smaller than 2, then I know that everything else in the array doesn't have to be compared to 1 right? 1, by being smaller the 2 is also smaller than 3. And also smaller than 6. So I'm taking a shortcut here that by knowing that 2 is larger than 1, I also know that everything else in that array is also bigger than 1.

[00:02:09]
So I'm skipping a bunch of comparisons that I otherwise would have to do. And the more and more things I throw at Mercer sort so if this ends up being of length 200 and this is of length 200. If one is smaller than two, then I know that I don't have to compare one to the other 199 elements in there right?

[00:02:28]
I'm skipping a lot of comparisons. So you could say this grows logarithmically, right. By having more and more I get the economies of scale and I don't have to make all those comparisons. So I still have to look at everything once. Every number gets looked at which says that it's end, right?

[00:02:51]
But I don't have to compare every number to every other number, which is not, means I don't quite get to n, I get to log n. So that's the big O of this computational or this time complexity here is n log n. Let's see how I wrote that.

[00:03:09]
So I don't know where it is anyway. This is n log n computational complexity. Because you have to look at everything at least once. That's just the virtue of sorting is that every number has to be at least looked at, which means that you're looking at everything once.

[00:03:27]
But you're not comparing one thing to everything else which makes it log n. As opposed to Insertion Sort, which it's worst case scenario. Every number is compared to every other number. That's why that's n squared. So the trick here for n log n kind of sorting scenarios is that you're looking for recursion.

[00:03:49]
It's not always gonna make it log n but very frequently makes it log n. Okay, spatial complexity, notice here that we're creating a lot of arrays, right? We're breaking up one array down into a bunch of other arrays. That means that we are no going to have constant spacial complexity, we're actually going to have some spacial complexity here.

[00:04:16]
In fact, mercer ends up being one of the worst ones because if you look here, every number gets at least one array created for it. So if it's a one-to-one mappings that means it's n right? So it's spatial complexities its' n. So for example, if you're on the ps3 and we were sorting huge numbers of numbers merge sort might be a bad idea, right?

[00:04:42]
Because it uses so much space. Might not be, but who knows. So space complexity is n. All right, so let's pop over to our code sandbox. We're gonna be here in Merge Sort. The sort visualizer will not work for merge sort or quick sort, because I didn't have a good way of breaking down the snapshots very well.

[00:05:18]
So I just didn't try. So why don't we go ahead and give Mercer sort a shot? What let's just like quickly go over the base case, the base case is what you get an array of length 1 or 0. It should always be length 1 but just say length 1 or length 0.

[00:05:39]
Then you just return that array. You don't do anything to it. That's the base case. You're gonna have to split the array into, you're gonna call merge sort on the left side, you're gonna call merge sort on the right side. And then you're gonna write another function const merge equals sorted array 1, sorted array 2.

[00:06:02]
And that is going to return one sorted array. Let's actually just I'm going to just diagram this out for you. Here are you going to base case Return if length 1 or 0. Break into two smaller arrays. Call, mercer sort on left and right. Here, I'm just using terms left and right.

[00:06:40]
You can call them array one, array two, array A, array B. I don't know why I like having some like cardinality to it of like this goes left, this goes right. In reality that doesn't make a difference. It does make a difference in Quicksort it doesn't emerge sort, okay?

[00:06:57]
And then you're gonna return the merge of left and right. So the first thing we want to work on is the base case, right? So, If nums.length is less than 2. So if it's of length 1 or length 0 cuz you can't have length negative of arrays, then we're going to just return.

[00:07:26]
It's already sorted but we're not gonna do anything. I think to it. This is the base case. Everything's good. I'm going to break this into a little bit easier to read logic here. So I'm going to say cons length equals num sort length. Cons middle equals math.floor length divided by 2.

[00:07:57]
So math dot floor if you don't remember, always rounds down on a number right? So if this is of length 7, then middle is going to come back as 4. Constant left equals nums.slice, 0 to the middle. slices, if you don't remember is going to return to a sub array.

[00:08:25]
So this is going to be the smaller left array which is gonna be from zero to the middle of the array. And then const right is going to be nums slice. And we can if we just give it middle, then it'll automatically go to the end, right? So this is gonna be everything on the left.

[00:08:45]
This is gonna be everything on the right Now you say const sorted, left equals merge. Sort left, const sorted, right equals merge, sort, right? And then down here, we're just gonna say return, merge, sort of left, sorted, all right. Cool? That is all you need to do. Put this above here so the comments are in the right place.

[00:09:42]
That's all merge sort is break things down into smaller arrays and then merge them back together. So, merge, I'm just going to call this left and right, that's a bit easier for me to think of. But just again, just reiterating and I keep repeating and the reason why I keep repeating this because I forget.

[00:10:02]
Left and right are already sorted. Just let's make a be abundantly clear it's you need to merge doesn't work if left and right aren't already sorted. So you don't have to handle the case of what happens if left or right is unsorted. That means something else broke, something else broke somewhere else.

[00:10:24]
Okay const results. There's gonna be an empty array. And then I'm gonna do this with kinda a fun way, which I'm gonna say while left.length and right.length. And I'm gonna say if left of 0 is less than or equal to right 0. Okay, then we're gonna say results.push, so we're gonna put on the end the front of left.

[00:11:08]
So we're gonna say left.shift. And again, JavaScript has weird naming for these kind of things shift is like popping off the front right? CF pop which removes the last item of the array and returns it. Shift does it from the front, right? Other languages will call this dq, right?

[00:11:29]
I guess it depends depends on what the language is trying to do anyways. Suffice to say shift removes the first item in the array and returns it. So this is gonna take the front item off of the left and push it on the end of results, okay? Else, we're gonna say results.push, right.shift, because we're not taking the left thing, we're gonna take the right thing, okay?

[00:11:57]
Now again, we're removing things from left and right eventually we're going to run out of things right? Either left is going to empty or right is going to empty first right? One of them by definition of what we're doing here. This is gonna break and one of them is still gonna have stuff left in it.

[00:12:15]
So what we can do after that is we can say return results.concat left and right. Now why does this work? Results is gonna be an already sorted list that was building, and one of left and right is gonna be empty, right? What happens if you call a concat on an empty array?

[00:12:40]
Nothing, right, nothing happens cuz it's empty and there's nothing to concat. So one of these is just going to concatenate all of its numbers, right? And we know everything that's left is going to be larger than what's already in results because it's at the end of that array.

[00:12:53]
So it makes sense. I mean you can have this keep going until they both have. If you did this instead or, You'd have to mess around here with the if logic to say like, if left out length and right.length and left is smaller than right, right? Then do that.

[00:13:20]
But we don't have to do that because we're just going to do this concut down here and this'll work. Okay, that is all of merge sort. I mean, that's what nine to. 30 some odd lines of code, some of the white-space it's, I mean, let's go ahead and run and make sure that I'm not pulling your leg here.

[00:13:53]
But if we go down to merge sort doesn't feel like running it right now. Merge sort, and I'm doing skip down here. So that's actually correct. And now I try running it again. Merge sort is passing. So again this is hard, right? If you didn't quite get it, or if you struggled with this, there's a lot of abstract stuff going on here.

[00:14:26]
And I can only do this with some ease because I've done this so many times. Because I've taught it to a lot of people.