0:00

[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.

Â 8:09

It's very, it feels really good to see it in action in front of you.

Â But, it is a bit tricky because it is using this principle of recursion.

Â And so, what we're focusing on in this module of the course isn't so

Â much an in-depth analysis of recursion.

Â But rather an illustration of the different possible

Â algorithms that are out there.

Â For solving the same problem,

Â and then thinking about how that translates to different performance.

Â So, let's think about that performance.

Â Let's think about how we might analyze how long it takes merged sort to run.

Â How many operations are required.

Â And so if we think about this algorithm,

Â really at the beginning all we were doing is saying I don't want to sort yet.

Â I don't want to sort yet,

Â I'm just going to define my problem and smaller subproblems.

Â And so we were organizing our data until the step where we had to merge.

Â That's where we starting doing comparisons between list elements and

Â really putting them together.

Â And at each level of the recursion once we started merging the sorted lists,

Â what we had to do was compare, pair-wise, basically all the elements.

Â But only once, each of them, were we comparing it with another element.

Â And so if we count how many comparisons are required there, it's O(n).

Â Where n, remember, is our input size, the size of the list that we started with.

Â So really where we were doing a lot of work was at a single level, merging

Â all those smaller lists together and figuring out how to maintain the order.

Â Okay. So then the question is, how many times

Â did we have to do this big merge step, and the number of times that we have to do

Â the merge step depended upon how many times we had to divide the lists in half.

Â And to get them into smaller and smaller chunks so that we could sort them.

Â Okay, so each time that we divide, we got two smaller lists.

Â So if we started with a list of size five, when we divided we got

Â lists of size two and three and then smaller and smaller and smaller.

Â And we got to stop.

Â When all our lists were of size 1.

Â So we had to keep dividing until all of our lists were of size 1.

Â And so we're asking ourselves how many times do we have to keep dividing by two.

Â If we start at n, I want to get all the way to 1.

Â But that's exactly the logarithm base, too.

Â So when you start at a number and you wanna keep dividing by 2, dividing by 2,

Â dividing by 2, and count how many times we have to do that until we get to 1,

Â that's log base 2.

Â And so what we're seeing here is that we have log base 2 of

Â n many times that we had to break down our problem into sub-problems, and

Â for each one of those, we had to do a merge step.

Â So, each one of those recursion levels

Â we had about O(n) work to merge all of the little pieces of lists.

Â And that repeated log n times.

Â And so our total performance is n times log n, or O(n log n).

Â