Merge Sort Solution

[00:00:00]
>> Speaker 1: So mergeSort, we have our base case here. When your array is a sorted list of length one, we are gonna return that. A couple other things that we need to do is we're going to find the middle. We're gonna slice it into a left and right side.

[00:00:16]
And then we're going to recursively merge the left and the right. Previously, we did something like this where we said,
>> Speaker 1: We said sortedLeft. This is how we had it before. And I'll put it like that, so that it's a little bit easier.
>> Speaker 1: So we'll just merge the sortedLeft with the sortedRight just to keep it a little more consistent with the pseudo code that we were going through earlier.

[00:00:56]
All right, and here's our merge routine, which we have outside of our defined function.
>> Speaker 1: So you can see how we're keeping track of our left and our right indices as we are pushing. We push, we increment, we push, we increment that one until they're all empty, they're both empty.

[00:01:30]
>> Speaker 1: Okay, we also wanna say about this. So the way this executes is exactly as we went over in the pseudocode.
>> Speaker 1: Yeah, here it is for your viewing pleasure.
>> Speaker 1: Mergesort.
>> Speaker 1: What's the most complicated thing to you about Mergesort?
>> Speaker 1: Is it the recursion, is it the merging part?

[00:02:12]
>> Speaker 2: It's the recursion that also calls the different function.
>> Speaker 1: Mm-hm, so we have this forking recursion, which is a little bit different than our other recursive examples. We weren't forking, right? So we recursed left and recursed right, yeah.
>> Speaker 2: We may think hypothetically it makes sense. It's really more the code part of it.

[00:02:34]
There are just so many detail. How do you keep track of all of the moving parts?
>> Speaker 1: Mm-hm.
>> Speaker 2: That's where, for me, it's hard to wrap my brain around that. But I understand how it works in theory, when you show the diagram of it.
>> Speaker 1: Yeah, yeah, yeah.

[00:02:46]
>> Speaker 2: It's the implemetation that's the-
>> Speaker 1: [CROSSTALK] Yeah, absolutely, and that's one of those things, yeah, it comes with doing this translation from, okay, here's a pretty picture. How do we translate that into real code? We're drawing boxes, but what does that box represent? What is that native structure?

[00:03:03]
We have these arrows pointing, what does that arrow mean? Is that a function call? Is that a loop? So these are all important things to get some practice on. But yeah, I agree that that's the most complex part for most people is to make that leap.
>> Speaker 2: So what it would be the real test case for it, right, or use case for it?

[00:03:27]
Like what would you like, you know what? Mergesort is exactly the solution that I need in this particular-
>> Speaker 1: So Mergesort is one of the best sorts. So if you ever need to sort anything for an interview, Mergesort is probably what they're looking for. Quick sort is what JavaScript uses under the hood.

[00:03:45]
I think it might also sometimes use Mergesort, depending on the scenario. But yeah, pretty much if you wanted to impress an interviewer over the sorting question, you can always implement Mergesort. However, my interviewing strategy in general is to start with a simple answer. Reference the more complicated answer, but not necessarily jump into implementing Mergesort.

[00:04:15]
In a high-pressure scenario, there's a lot of ways it could go wrong. And you wanna optimize it for things going right. So you could say something like, is it all right if I start with a naive sorting algorithm like bubble sort? i understand that in a lot of cases it's quadratic time.

[00:04:33]
And it would be better to do maybe something like Mergesort, which is n log n. However, I think within the time constraints of our interview, it would be easier if I just went with a bubble sort. Or you can just not even talk about Mergesort, implement it in bubble sort.

[00:04:49]
Say that you could do better by doing a divide and conquer sort. So acknowledge that you understand you've heard of it. But try to avoid implementing it. This is my strategy. Just because if you see it's quite a bit of code. You could do off by one. There's a lot of situations where, here's another place we go off by one.

[00:05:20]
There are a lot of places where you can mess it up. So I think if you can get away with it, don't do this. But if you're really good at it and you wanna get really good at it, then yeah, that would be very impressive to do Mergesort.

[00:05:34]
I would be impressed if someone did a Mergesort in one of my interviews. But I don't ask those kinda questions. But big companies do. Mm-hm?
>> Speaker 2: Can I ask you what, give us an example of what people ask you during the interview where you have to use a sort to answer it?

[00:05:53]
>> Speaker 1: Yeah, I would just say you have an array of unsorted integers, sort them.
>> Speaker 2: That's just mostly the case, right?
>> Speaker 1: Mm-hm.
>> Speaker 2: They're not gonna go really complex?
>> Speaker 1: Well, so for example, there might be code words for you have a list and maybe you have timestamps.

[00:06:19]
Or you're filtering by the oldest timestamps. And so like the thing that you're comparing might not be an integer. It could be a date or something. Yeah, what else? Yeah, and I think so there are other scenarios where if your list is sorted, for example like a binary search, so if your list is already sorted, then that helps you.

[00:06:51]
And so you can always do the JavaScript native sort as well. You just have to remember if it's a comparison sort with numbers, you need to remember that callback. What you do, you call a, b, a- b. Remember that, and then you can get around all of this raw implementation detail.

[00:07:11]
But there are some scenarios where having a list that's sorted will make your algorithm faster, like for a binary search. So if you're trying to search, you say, okay, well, can I sort it first? Once it's sorted, it can speed things up. Or you could get it sorted, that's nice, too.