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 simpler
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 in numbers, the merge sort algorithm
needs no more than a constant times N log
N operations. That's the maximum number of
lines of executable code that will ever
execute specifically six times n log n
plus six n 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 of 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,
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 gonna call this level
zero. Now this tree is going to be binary
in recognition of the fact that each
indication of Merge Sort makes two
recursive calls. So the two children
will correspond to the two recursive calls
of Merge Sort. So at the route, 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 the level two recursive calls,
of which there are four, and this process
will continue until eventually the
recursion bottoms out, in base cases when
they're only an array size zero or one. So
now I have a question for you which I'll,
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 guess,
correctly guess, 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 array
of size n over two, at level two,
each array has size n over four, and so on.
Where does 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 two, until you get down to a
number that's most one. Recall that's
exactly the definition of a logarithm base
two of n. So since the first level is
level zero and last level is level log
base two of n. The total number of levels
is actually log base two of n plus one.
And when I write down this expression, I'm
here assuming that N is a, is a power of
two. Which is not a big deal. I mean the
analysis is easily extended to the case
where N is not a power of two. And this
way, we don't have to think about
fractions. Log base two of N then is an
integer. Okay so let's return to the
recursion tree. Let me just redraw it
really quick. So again, down here at the
bottom of the tree we have the leaves,
i.e. The base cases where there's no more
recursion. Which when N is the power of
two correspond exactly to single element
arrays. So that's the recursion tree
corresponding to an indication of Merge
Sort. And the motivation for writing
down, for organizing the work performed by
Merge Sort in this way, is it allows us
to count up the work, level by level. And
we'll see that 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 to 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 a-, of
the array, which is passed to a
sub-problem 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 two to
the j distinct sub-problems. There's one
outermost sub-problem at level zero, it
has two recursive calls, those are the
two, sub-problems at level one, and so on.
In general, since merge short calls itself
twice, the number of sub-problems is
doubling at each level, so that gives us
the expression, two to the j, for the
number of sub-problems at level j. On the
other hand, by a similar argument, the
input size is halving each time. With each
recursive call you pass it 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 of N, after J levels,
each sub-problem will be operating on an
array of length N over two to the J. Okay,
so now let's put this pattern to use, and
actually count up all of the lines of code
that Merge Sort executes. And as I said
before, the key, 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 Merge Sort, not
counting their respective recursive calls.
Not counting work which is gonna get done
in the recursion, lower in the tree. Now,
recall, Merge Sort is a very simple
algorithm. It just has three lines of
code. First there is a recursive call so
we're not counting that, second there is
another recursive call again we're not
counting that a little j and then third we
just invoke the merge subroutine. So really
outside of the recursive calls all that
merge sort does is a single invocation 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 gonna 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 sub-problems there
are, two to the j. We know the size of
each sub-problem, n over two to the j, and
we know how much work merge needs on such
an input, we just multiply it by six, and
then we just multiply it out, and we get
the amount of work done at a level j.
'Kay? And all of the little adjacent
problems. So here it is in more detail.
Alright. So. We start with just the number
of different sub-problems at level J and
we just notice that, that was at most two
to the J. We also observe that each level
J sub-problem is passed an, an array as
input which has length N over two to the
J. And we know that the merge subroutine,
when given an input, given an array of
size, N over two to the J, will execute
almost six 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
 sub-problem, per sub problem. And
then something sort of remarkable happens,
where you get this cancellation of the
two, two to the Js. And we get an upper
bound 6N. Which is independent of the
level J. So we do at most six end
operations at the root, we do at most six
end operations at level one, at level two,
and so on, okay? It's independent of the
level. Morally, the reason this is
happening is 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 2ndly the amount of work that we
do per sub-problem is halving with each level
of the recursion tree's, once those two
cancel out. We get an upper bound 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 Merge Sort 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 based
two of N plus one. Remember the levels are
zero through log based two of N inclusive.
And then we have an upper bound 6N for
each of those log n plus one levels. So if
we expand out this quantity, we get
exactly the upper bound that was claimed
earlier namely the number of operations
merge sort executes is at most 6n times
log base 2 of n plus 6n. So that my friends,
is a running time analysis of the merge
sort algorithm. That's why it's running
time is bounded by a constant times N log
N which, especially as N grows large, it
is far superior to the more simple
iterative algorithms like insertion or
selection sort.