Placeholder Image

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