In this video we'll be giving a running time analysis of the merge sort algorithm. In particular, we'll be substantiating the claim that the recursive divide and conquer merge sort algorithm is better, has better performance than simple sorting algorithms that you might know, like insertion sort, selection sort and bubble sort. So in particular, the goal of this lecture will be to, mathematically argue the following claim, from an earlier video. That, in order to sort an array of n numbers, the merge sort algorithm needs no more than a constant times n log in operations. That's the maximum number of lines of code it will ever execute. Specifically 6 times n log n + 6n operations. So how are we going to prove this claim? We're going to use what is called a recursion tree method. The idea of the recursion tree method is to write out all over the work done by the recursive merge sort algorithm in a tree structure with the children of a given node corresponding to the recursive calls made by that node. The point of this tree structure is it will facilitate a interesting way to count up the overall work done by the algorithm and will greatly facilitate the analysis. So specifically what is this tree? So at level zero we have a root. And this corresponds to the outer call of merge sort, okay so I'm going to call this level zero. Now, this tree is going to be binary in recognition of the fact that each invocation of MergeSort makes two recursive calls. So the two children will correspond to the two recursive calls of MergeSort. So, at the root we operate on the entire input array, so let me draw a big array indicating that, and at level one we have one sub problem for the left half and another sub problem for the right half of the input array. And I'll call these first two recursive calls level one. Now, of course, each of these two level one recursive calls will themselves make two recursive calls. Each operating on then a quarter of the original input array. So those are level two recursive calls of which there are four. And this process will continue until eventually the recursion bottoms out in base cases when there's only an array of size zero or one. So now I have a question for you which I'll give you in the form of a quiz. Which is at the bottom of this recursion tree corresponding to the base cases, what is the level number at the bottom? So at what level do the leaves in this tree reside? Okay, so hopefully you guessed, correctly guessed that the answer is the second one. So namely that the number of levels of the recursion tree is essentially logarithmic in the size of the input array. The reason is basically that the input size is being decreased by a factor two with each level of the recursion. If you have an input size of n at the outer level, then each of the first set of recursive calls operates on a array of size n over 2. At level two, each array has size n over 4 and so on, whereas if the recursion bottom out, well, down at the base cases, where there's no more recursion, which is where the input array has size one or less. So in other words, the number of levels of recursion is exactly the number of times you need to divide n by 2, until you get down to a number that's most one. And recall, that's exactly the definition of a logarithm base 2 of n. So since the first level is level zero and the last level is level log base 2 of n. The total number of levels is actually log base 2 of n plus 1. And when I write down this expression I'm here assuming that n is a power of 2 which is not a big deal. I mean the analysis is usually extended to the case where n is not a power of 2. But this way we don't have to think about fractions log base 2 of n then is an integer. Okay, so let's return to the recursion tree, and let me just redraw it really quick. So again, down here at the bottom of the tree, we have the leaves. And i.e., the base cases, where there's no more recursion. Which, when n is a power of 2, correspond exactly to single element arrays. So that's the recursion tree corresponding to an invocation of MergeSort. And the motivation for writing down, for organizing the work performed by MergeSort in this way, is it allows us to count up the work level by level. And we'll see that's a particularly convenient way to account for all of the different lines of code that get executed. Now to see that in more detail, I need to ask you identify a particular pattern. So first of all, the first question is, at a given level j of this recursion, exactly how many distinct sub problems are there as a function of the level j. That's the first question. The second question is, for each of those distinct sub problems at level j, what is the input size. So what is the size of the array which is passed to a subproblem residing at level j of this recursion tree? So the correct answer is the third one. So first of all at a given level j, there's precisely 2 to the j distinct subproblems. There is one outermost subproblem at level zero. It has two recursive calls. Those are the subproblems at level one, and so on. In general, since MergeSort calls itself twice, the number of subproblems is doubling each level, so that gives us the expression 2 to the j for the number of subproblems at level j. On the other hand via a similar argument the input size is halving each time with each recursive call you pass at half of the input that you were given. So at each level of the recursion tree we're seeing half of the input size of the previous level. So after j levels since we started with an input size n after j levels each subproblem will be operating on an array of length n over 2 the j. Okay so now let's put this pattern to use, and actually count up all of the lines of code, and thenMergeSort executes. And as I said before, the key idea is to count up the work level by level. Now to be clear, when I talk about the amount of work done at level j. What I'm talking about is the work done by those 2 to the j invocations of MergeSort not counting their respective recursive calls, not counting work which is going to get done in the recursion lower in the tree. Now recall merge sort is a very simple algorithm, it just three lines of code, first there's a recursive call so we're not counting that, second, there's another recursive call. Again, we're not counting that at level j. And then third, we just invoke the merge subroutine. So really outside the recursive cause all that MergeSort does is a single indication of merge. Further, recall we already have a good understanding of the number of lines of code that merge needs. On an input of size m, it's going to use at most 6m lines of code. That's an analysis that we did in the previous video. So let's fix a level j. We know how many subproblems there are, 2 to the j. We know the size of each subproblem, n over 2 to the j. And we know how much work merge needs on such an input. We just multiply by 6. And then we just multiply it out. And we get the amount of work done at a level j. Okay at all of the little j subproblems, so here it is in more detail. All right so, we start with just the number of different subproblems at level j and we just noticed that that was at most 2 to the j. We also observed that each level j subproblem is past an array as input which has length n over 2 to the j. And we know that the merge subroutine, when given an array of size n over 2 to the j, will execute at most 6 times that many number of lines of code. So to compute the total amount of work done at level j, we just multiply the number of problems times the work done per subproblem. And then something sort of remarkable happens. We get this cancellation of the two 2 to the j's and we get an upper bound 6n which is independent of the level j. So we do at most 6n operations at the root. We do at most 6n operations of level one, at level two, and so on okay. It's independent of the level. Morally, the reason this is happening because of a perfect equilibrium between two competing forces. First of all, the number of subproblems is doubling with each level of the recursion tree. But secondly, the amount of work that we do per subproblem is halving with each level of the recursion trees. And so those two cancel out. We get an upperbound 6n, which is independent of the level j. Now, here's why that's so cool, right, we don't really care about the amount of work just at a given level. We care about the amount of work that MergeSort does ever at any level. But if we have a bound on the amount of work at a level which is independent of the level, then our overall bound is really easy. What do we do? We just take the number of levels. And we know what that is. It's exactly log base 2 of n + 1. Remember, the levels are zero through log base 2 of n inclusive. And then we have an upper bound 6n for each of those log n plus 1 levels. So, if we expand out this quantity, we get exactly the upper bound that was claimed earlier, namely that the number of operations MergeSort executes is at most 6n times log based 2 of n plus 6n. So that my friends, is a running time analysis of the merge sort algorithm. That's why its running time is bounded by a constant times nlogn, which especially has n grows large, it is far superior to the more simple iterative algorithms like insertion or selection sort.
