This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Exercise 4: Merge Sort" Lesson
[00:00:00]
>> [MUSIC]
[00:00:03] Let's pull up the exercise. Does anyone have any questions so far? Like what we've done so far. Yeah?
>> Yeah, one question. In your example, the two lists that you have, once you've compared six to seven then you just add the last two, seven and eight on but what if it was seven and four in that order.
[00:00:33]
>> Seven and four?
>> So, if the second one was two, seven, four then eight is never been hit. In this case, so substitute 8 for 4 would have been compared against.
>> So let me draw on this to see if I get, make sure I get this right, okay.
[00:00:55] Screensoft, So you're saying So here we're not gonna have 8, we're gonna have 4, is that-
>> Correct.
>> Okay, so you're gonna say, I'll just walk through the whole algorithm with you. So compare 1 to 2, take 1, compare 2 to 5, take 2, compare 5 to 7, take 5, compare 6 to 7, take 6.
[00:01:23] This is the fundamental flaw in what you're saying, is because this list has to be sorted. Before it gets to you, it's always gonna be sorted and you can make that assumption that it's always gonna be sorted by the time it gets to you. If it's not sorted, something else in your code is broken.
[00:01:40] So you need to fix that to make sure that it gets to you sorted. So yes, good question. Yeah. Great. So something I'm not sure if I covered it but just to say it again. One of these list is going to run out first, just right? One of them is going to run out of elements to put into your array.
[00:02:12] And so if A comes first then you put all the rest of the, let me figure out what I'm trying to say. So list 1 runs out first, then you add everything from this 2, if list 2 runs out first, then you add everything from list 1, right?
[00:02:26] That's what I was trying to say. Because you have no guarantee of list 1 or list 2 having more elements or greater elements or anything like that that you just know that you have two lists right. Or another words you can swap list 1 and list 2 in this equation and that's a total possible scenario.
[00:02:49] Okay, so I’ve again recap here what you are supposed to do. You're gonna do something that does merge sort, so call your function merge sort. It's gonna take in an array of numbers and return a sorted array of numbers. If you want to read the stitching algorithm just grab it off of the page that we' just were on.
[00:03:13] I don't have any visualization for this part, just so you know so, you're on your own to do the console log or whatever you want to do. I would definitely recommend changing it to X describe instead of describe because, or else you're going to stack overflow and everything's going to crash and everyone's going to die, don't do that.
[00:03:35] And yeah, any questions about merge sort or the requirements or anything like that? Another trick with Code pen they just added which I don't know too much about it. We actually do have a console down here that you can use. So if I say like up here console.log hi.
[00:04:00] Should show up down here right? So if you, yeah, console.log will show up there. I'm also pretty sure they will show up in your normal JavaScript console, which they do. Your JavaScript console gets really noisy with code pen though so I tend to ignore it and I tend to just use the console here.
[00:04:23] Okay, so just to reiterate this is a difficult problem, so if this seems difficult it's because it is difficult. So feel okay, if you don't necessarily get it the first time, right? It might take you a couple times to wrap your mind around everything that happens. But again, write your merge sort and that's a good place to start.
[00:04:44] Write merge sort that just breaks one list into two smaller lists of roughly equal sides, if it's of list size five one side's gonna get three, one side's gonna get two, doesn't matter which side. Just be consistent about it, and then take those lists and break them into smaller lists, that's the first place to start.
[00:05:06] Get your list broken into lists of one, and then once you're at that point then start writing your stitch algorithm that's going to stitch those smaller arrays back together in a sorted way.