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

I must know that everything on the right has

to be bigger than everything that's in the merged array right now.

So instead of saying, OK, I'll put four in and then I'll put six in,

because the only thing left is on one side, everything must go.

So that all comes down.

And let's again take a second and think about where we are.

At this point, for the original brick red array that we started with,

we have gone through two of our pseudocode steps.

We've sort of the left half of that overall brick red array.

And we've sorted the right half of that overall brick red array.

And so now the final thing we have to do is merge those two halves together.

And just like before, we continue to ask ourselves the same question again.

Which is lower, one or three?

Notice the little black line there dividing the two halves to make it more

visually clear.

Which is lower, one or three?

Well, one is.

Now again I ask myself the question, which is lower, two or three?

That would be two.

Which is a lower, five or three?

That's three.

Five or four?

It's four.

Five or six.

It's five.

Six or nothing?

It's six.

And so by going through this process recursively

and breaking my problem down into smaller and smaller sub-arrays,

sorting those, merging them together, after a number of steps,

I have now completed my sort.

And I have everything in order here in dark blue.

One, two, three, four, five, six.

It's not necessarily as straightforward as something

like bubble sort, insertion sort, or selection sort.

But are there some advantages here?

Well, the answer is, yes, there are.

In the worst case scenario, we have to split up n elements.

And then we have to recombine them, effectively doubling the sorted arrays

as we build them up.

So we take two one-element arrays, and we turn it into a two-element array.

We take two two-element arrays.

We make it into a four-element array.

And so on and so on and so on as we go.

In the best case scenario, sort of like selection sort,

the array is already sorted, but we don't know this.

We don't know this until we split it and recombine it back with this algorithm.

There's no sort of shortcut here other than doing a search beforehand.

But that's going to add extra time as well.

So the result here is that we have n elements--

and we might have to combine them if we're doubling-- log n times.

Mathematically, that's how it works.

And so actually, unlike the other algorithms

we've covered, in the worst case scenario, the runtime of merge sort