 ## Subtitles section Play video

• [MUSIC PLAYING]

• DOUG LLOYD: All right, so by now we've talked

• about a couple of different sorting algorithms that

• are pretty straightforward to work with, hopefully.

• We've got bubble sort, insertion sort, and selection sort.

• And what we do know is what all of have in common

• is that they have a sort of worst case scenario runtime of n squared.

• Can we do any better than that?

• Well, the answer happens to be yes, we can,

• using an algorithm called merge sort.

• Now in merge sort, the idea is to sort smaller arrays

• and then combine those arrays together or merge them,

• as in the name of the algorithm itself, in sorted order.

• So instead of having to think about, we have one six-element array,

• let's think instead that we have six one-element arrays,

• and then let's just recombine them in the correct order

• and merge them together.

• That would be one way to sort it.

• And that's what merge sort does.

• And it leverages something called recursion, which

• we'll talk about soon in another video.

• And if you want to get a better understanding of how recursion works,

• you might want to take a look at that video

• before coming and watching this one, because this is going

• to talk about recursion quite a bit.

• Merge sort is definitely the most complicated

• of the four different types of sorts that we cover in the class.

• And so I'm going to go through this one a little more slowly

• than the other ones.

• But the algorithm for merge sort itself is actually pretty few steps.

• We're basically going to say, we're going

• to sort the left half of the array, sort the right half of the array,

• and then merge the two halves together.

• That is fundamentally what merge sort is all about.

• Of course, in practice, it's a little more detailed than that,

• but let's go through that now.

• So here's the same six-element array we've been sorting all the time.

• And we're going to start to follow our steps of pseudocode,

• which is we want to sort the left half of this brick red array.

• So we're just going to focus on this part for now.

• And actually, just to make things a little bit easier,

• and because I've colored different things in different ways

• throughout this video, we're going to refer

• to this half of the array, this left half of the overall red array,

• from this point forward, this is the purple half of the array.

• All right?

• So we are now in the middle of sorting the left half of the array.

• But we don't know how to do that.

• We don't know how to sort the left half of the array.

• So why don't we just go back to our merge sort steps again?

• All right, well, if I don't know how to sort the left half of the array,

• I'm just going to start again.

• Sort the left half of this array.

• Now I just want to focus on this part of the array, the left half.

• And I'm sort of arbitrarily deciding that my left half is

• going to be smaller than my right half.

• I have three elements.

• I can't divide it evenly.

• I can't have one and 1/2 elements on each side.

• So as long as I'm consistent, as long as I always choose, in this case,

• the left side is smaller, that will be fine for merge sort's purposes.

• So now I'm left with this single element, this five.

• How do I sort a one-element array?

• Well, the good news here is I actually don't have to sort it at all.

• A single-element array must necessarily be sorted.

• So I can say that if I'm sorting the left half of the purple part,

• that is sorted.

• So we're just going to call that sorted and set it aside for now.

• So now I want to go back to the right half of the purple part.

• That's this.

• How do I sort this array, this sub-array?

• Let's just go back to our steps again.

• I want to sort the left half only.

• The left half is now two.

• It's a single element.

• I know how to sort a single element.

• So I've sorted the left half of this, the left half

• of the right half of the purple.

• That's where we are.

• That's sorted.

• Now I go back and sort the right half of the left half

• of the purple, which is the one.

• One is a single element.

• It's really easy to sort.

• It's in sorted position.

• Now is the first time I finally get to this third step of merge sort,

• where I merge the two halves together.

• So here, what I have to do is consider these two light green halves.

• And I have to decide which one has the lower element.

• In this case, it's one.

• So what I do is I take the one and I put it

• in the first position of some new hypothetical array.

• Then I compare the two against nothing, and I ask which one is lower.

• Well, two or nothing.

• What's lower is two.

• So now let's reframe the picture, because if we remember

• talking about recursion, we're only focusing

• on the left half of the overall brick red array,

• which we then called the purple array.

• By this point in our steps, with respect to the purple array,

• we have sorted the left half, which is five,

• and the right half, which was originally two and one,

• but now we have done these merging steps,

• and we've got that in the correct order.

• So now we are on step three for the entire purple array,

• because we've already sort of the purple array's left half

• and the purple array's right half.

• So now we need to merge these two halves together.

• And just like we did a second ago with the two and the one,

• we're going to compare the first element of the left part

• and the first element of the right part and figure out which one is smaller,

• and make that the first element of our new array.

• So I compare five and one.

• And I say, which one is smaller?

• Well, it's one, so one becomes the first element

• of this new three-element array.

• Now I have to make another decision.

• Is five lower, or is two lower?

• Well, two is lower.

• So two becomes the next element of our merging step.

• Then I say, is five lower or is nothing lower?

• Well, clearly, in this case, the only option I have left is five.

• And so now, at this point in the process,

• let's again think recursively about where we are.

• We have sorted, for the entire red array, we have just done step one.

• We have sorted the left portion.

• We've done so recursively, but we have sorted the left portion

• of the overall red array.

• So we can kind of put this aside for now,

• because now we have to go to the next step of the merge sort process, which

• is to sort the right half of that red array.

• So let's go over and focus on the right half.

• We're going to go through exactly the same steps

• that we just went through with the left part.

• But now we're going to do it with this red part on the right.

• So I want to sort the left half of this array.

• Well, that's pretty easy.

• I just arbitrarily again divide it.

• I look at it.

• I say, OK, well, three is a single element.

• Single element is already sorted, so I don't

• have to do anything, which is great.

• I can just set that one aside and say, three is already sorted.

• Now I want to sort the right half of the not so brick red,

• but is still red, half of the array, which is this section.

• How do I do this?

• Well, it's more than one element.

• So I'm going to go back to the beginning of my process again.

• I'm going to sort the left half of that array.

• So I look, and I say, here's the left half.

• It's six.

• It's already sorted.

• Now I'm going to sort the right half of the array.

• It's four.

• It's already sorted.

• Now I get to that merge step again, where

• I have to again do these sort of side-by-side comparisons.

• Which one is lower?

• Is six lower, or is four lower?

• Well, four is lower, so that becomes the first element

• of our new merged little sub-array here.

• And then I have to choose between six and nothing.

• And I say, six is the lowest remaining.

• So now I've sorted the left half of the right half.

• And I've sorted the right half of the right half.

• So now I want to merge those two portions together.

• And again, we're going to do exactly the same process

• that we did for the left portion.

• I'm going to say, is three lower, or is four?

• Well, it's three.

• And then I'm going to say, is four lower, or is nothing?

• There's nothing left on the left side, then