[MUSIC]

So we've been talking about insertion sorting and selection sorting, and

we've been analyzing their performance.

And in this video we're going to talk about yet another algorithm

to accomplish the exact same task, which is sorting a collection of data.

And so by the end of this video, you'll be able to describe this algorithm,

the merge sort algorithm.

And the reason we're talking about it is because it's a very

different kind of algorithm from the ones that we've looked at so far.

And in particular, it uses recursion.

So you'll be able to explain how this particular algorithm uses recursion, and

then discuss its performance.

So let's start with a description of the algorithm and

how it goes about sorting a collection of data.

So we're presented with some input data and we think of it as a list.

And let's just think about the easiest case we might have.

And in the easiest case that list will only have one element.

And so if our list has just one element then really we don't need to do anything.

We can return.

Because just one element is already sorted.

There's nothing that could be out of place so

it's already all organized in ascending order.

Okay, so if we're in that special base case, the small case.

Then we're done, but if not then we actually have to do some work and

the merge sort algorithm says well,

I've got a big collection of data that I need to organize from smallest to biggest.

And that seems really hard so why don't I make my life a little bit easier and

just cut the list right in half.

And then I'll focus on say the first have of the collections of data and

say can I organize that piece.

Okay, maybe that's a slightly easier task because I've got fewer elements there.

And so I'll think about how to do that in a minute.

But, suppose I was able to organize that first half of the list.

Then I go ahead and say, well what about the second half of the list?

Can I organize that?

Can I sort it in order from smallest to biggest?

And again, that's a smaller collection than what I started with so

maybe it's a little bit easier.

And so once I do these two steps,

then I've got two smaller lists that are each sorted, and now what

remains is to somehow combine those two lists while maintaining the order.

And so I'd wanna merge the two sorted lists and then output the result.

And so we really haven't done any comparison of elements yet,

in this description.

But what we've done is described a high level strategy of how we might sort

of big list by dividing the problem into something a little bit smaller.

Sort the first half, sort the second half, and then merge the results

while preserving the order of the two smaller lists that are sorted.

Okay, so that seems like a plausible strategy, when we have a big problem,

break it down, divide and conquer.

But we've really kind of punted, we've postponed our solution for

how do we actually go ahead and sort these two smaller sublists?

We haven't said how we're going to do that, and

this is when something really powerful comes into play.

What we're doing here is using the power of recursion.

And what recursion is all about is breaking a big problem down

into a smaller subproblem and

then a manageable amount of work to incrementally change what we need to do.

So we had a big list to begin with, and we're going to

think about solving the problem on the big list as solving smaller,

similar subproblems and then combining the results.

And what's really helping us out here is that once was broken down the problem

into smaller and smaller and smaller list, eventually we know what to do because

eventually, if we get down to just a single element, then that list has sorted.

Okay, so, this all kinda feels a little bit abstract.

So, let's work through an example and see how it all plays out.

So let's think about a five element list.

And think about the numbers, the integers between one and

five that we've messed around a bit, and so they're not in order anymore.

And so we'd like to use the merge sort algorithm to rearrange the numbers in this

list and put them in order.

So, according to our merge sort algorithm, we first of all observe that this list has

more than one element, so we're not in the base case.

We have to do something, and

so we're going to divide the list in half and then sort the two halves.

So we start by dividing the list in half and so we've got the first half.

Well, half of 5 is two and a half and so we round down to two elements, and

then the rest of the list is in the second half.

And now we need to sort that first half, but sorting means using merge sort, again,

using our overall strategy, and so that means we start at the beginning and

we check, does the list that contained 5 and 3 have just one element?

No, it's got two.

So we need to divide that list in half again.

And so the list that contains 5 and 3 gets divided down into a list that

just contains 5, and a list that just contains 3.

And similarly the list that contained 2, 4, and 1, gets divided down into halves.

One that contains just the element 2, and then the second part of that list is

the list that contains the elements 4 and 1.

Okay and now what we want to do is

sort each of those halves that we got out of dividing our lists.

And so we look at that first half of the list, and that just has the element 5.

And so when we reach down to this base case of a list with just one element,

then that one list is already sorted so we can return.

And so when we've sorted the list five, well we don't need to do anything.

So the yellow shading indicates that that list is sorted.

And similarly the list that just contains 3 and the list that just contains 2.

When we look at the list it contains 4 and 1 and we try to apply merge sort to that

list in order to sort that half so then we can merge all the way back.

We notice that it has more than one element so

we need to divide it in half and then we'll be sorting each of it's halves,

but they're just one element list so they're already sorted.

Okay, so what we've done at this point is just broken down our problem over and

over again to narrow into the smallest sub problems that we can actually manage.

And so we've started with a big list and we've divided, and divided, and

divided in half until we get a whole bunch of lists that each have one element.

And so those one element lists are sorted.

But now we have to do that crucial step of merging the sorted lists

while preserving the order.

So let's think about what that happens.

We want to merge the lists 5 and 3,

and that means we're going to combine their elements.

The resulting list is gonna have two elements, but we want to do it in order,

so we choose to pick off the elements from the top of the list, or

the head of the list.

Based on which one is smaller.

And so we're going to start with the 3 because it's smaller, and

afterwards put in the 5.

And notice that what we got as a result is a sorted list, but it's a little bit

bigger than what we had before, and so it's bringing us one step closer to our

result, which is that sorted, five element array that we're looking for.

Okay, so we've combined two halves of a list that were part of our

recursive descent into the smallest sub problems, and now we keep on going.

So the 1 and the 4 get combined to a two element list and

then we add in that list two.

And notice that when we merge the list two with the list one four,

what's going to happen is that the 2 will get inserted between the 1 and the 4.

Because we're comparing the heads of the list at each point, and

making sure to merge those lists so that they preserve the order.

And so then what we have is a two element list on one side that's sorted.

And a three element list on the other side, also sorted.

And we're going to merge those.

And what we'll get is exactly the sorted array 1, 2, 3, 4, 5 that we want.

Okay, so this is a bit of a quick and

dirty high level description of the merge sort algorithm.

I encourage you to try implementing it.