- [Instructor] Merge Sort.
We start here on this slide with a photograph
of computing pioneer John von Neumann
standing next to part of one of the computers
he helped design.
I show his photo here because he was the inventor
of merge sort back in 1945.
Now merge sort is not like the other sorting algorithms
that you've seen so far.
It's a very different kind of animal.
Merge sort is a divide-and-conquer algorithm,
and divide-and-conquer algorithms
break down a problem recursively,
and then combine the results of subproblems
to produce the final result.
Now, let's think back to the first week of the course
when we covered recursion.
As you recall, recursive functions call themselves,
that's what makes them recursive,
and recursive functions require one or more base cases.
Without a base case,
a recursive function could call itself indefinitely,
and never terminate.
Hence we need the base cases.
The base cases are not recursive.
The examples we've seen earlier in the course
are Fibonacci and vectorial.
Let's refresh our memory with regard to Fibonacci.
The Fibonacci sequence starts with zero and one,
and then calculates subsequent terms by taking the sum
of the previous two terms in the sequence.
So a Fibonacci number, denoted F sub n,
where n is an index, is calculated thus.
F sub n is zero.
If n is zero F sub n is one.
If n is 1 then F sub n is equal to F sub n - 2
plus F sub n - 1 otherwise.
So these are our base cases,
and this is the recursive case.
And we can think of this as breaking the problem down
into smaller subproblems.
The nth Fibonacci number is the sum
of two smaller Fibonacci numbers,
F sub n - 2 and F sub n - 1.
And the solutions to these smaller problems
are combined to produce the final result.
Here, we combined the solutions to sub problems by addition.
But what about merge sort?
Well, merge sort breaks the problem
of sorting down into smaller subproblems.
This is done recursively.
Now we need a base case.
Base case is a vector of a single element.
The single element is sorted by definition.
Now that may seem trivial,
but it is, in fact,
the base case for merge sort.
And how do we produce a solution?
In the case of Fibonacci
we just added the two subsolutions,
but we can't do that when we're sorting.
So what do we do?
We merge.
And this is where merge sort gets it's name.
What is merging?
Well, here's a simple case.
We have 2 one element vectors,
and we merge them to produce 1 two element vectors.
Notice that both of the source vectors we're emerging,
are already sorted.
They're one element vectors,
and they are sorted by default.
Now you're probably thinking,
"Oh, that's just brilliant,
but how does this help me sort a vector
of a million elements?"
All I can say right now is bear with me,
it'll all become clear in time.
So here's a more complicated example.
Here we have to compare the single element on the left
with the single element on the right,
and we use this comparison to merge the elements
from the two source vectors in the correct order.
So far, so good.
Here's another example.
We've already merged 4 one element vectors
into 2 two element vectors,
and now we want to merge them into 1 four element vector.
Now this case is pretty simple.
But what if we wanted to write a function
that can merge any two sorted vectors
into a single, larger sorted vector?
How would that work?
Obviously it would have to be able
to handle a case like this,
but notice that the two input vectors are sorted already.
So, we can use that information.
We know those two input vectors are sorted.
So the smallest value in each will be the left-most position
so we can start there.
So let's begin by figuring out
what should be the first element
in the result vector at the bottom.
Now we just compare the two values
at the indicated positions in the source vectors,
and put that value into our result vector.
Simple, one.
Now what?
Well, we've used an element
from the right-hand source vector,
and we don't want to use that element again.
So let's move that arrow to the right.
And we want to move the arrow on the result vector
to point to the next empty position.
And now, we repeat what we did before.
We compare the elements indicated
by the arrows and the source vectors,
and choose the smaller of the two.
Here the value is two.
We put that into our result vector.
And then, we move the arrows as we did before and repeat.
Again, we choose the smaller of the two values three,
and put it into the result vector in the indicated position.
We've used up all the values in the left-hand source vector.
So we're not going to choose any more values
from that vector.
And, we only have one value to choose
in the right-hand side.
So we're gonna pick that to complete our result vector.
And our merge is complete.
Now that wasn't too difficult.
The important thing is that this process works just as well
with vectors of any size.
If we want to merge 2 million element vectors,
the process would be the same.
Take a little longer,
but the process would be the same.
Now, for efficiency's sake,
we can use a single vector as a source,
so long as it consists of two sorted subvectors.
So, let's expand on our example just a bit.
Here we have our two input vectors,
actually they're sorted subvectors of four elements each,
and we want to merge these into a single vector
of eight sorted elements.
We need to keep track of where our subvectors begin and end
so we know which is the left subvector,
and which is the right subvector.
And so, the input on the left-hand side starts at start,
we're calling that position start,
and runs to middle.
And the input on the right-hand side
runs from middle plus one to the end.
Then, as before,
we have three indices,
one into the left-hand input,
we'll call that i,
one into the right-hand input,
We'll call that j,
and one into the result vector,
We'll call that k.
So i, j, and k.
With this setup, everything proceeds as it did
in our earlier example.
What goes into position k?
The smaller of the values indexed by i and j.
In this case one.
We increment our indices,
adding one to j and one to k.
What's next?
Well, two's smaller than three so we choose two
from the right-hand side.
And we increment our indices.
What's next?
We choose three from the left-hand side,
and we increment the appropriate indices.
Now four from the right-hand side.
Five,
six,
seven from the right hand side,
and eight from the left-hand side.
And now we can copy the values that we've produced
back to the original input vector,
and we have a sorted, merged vector.
So merge sort works by breaking the problem down
into single-element vectors,
or single-element subvectors,
as the case may be.
And then building a solution through successive merges.
And merging really is at the heart of this algorithm.
Breaking the problem down into its components
is almost trivial.
So here's the big picture.
The algorithm splits the input into one element vectors.
A one element vector represents the base case
in the recursions.
And so one element vector is already sorted.
And then using the merge algorithm we just saw,
merge sort builds the solution from the subsolutions.
Divide-and-conquer.
You probably know the Simpsons,
and this was intended as a gag,
but if you look carefully,
Marge sort is exactly the same thing as merge sort.
And this diagram is an accurate depiction of merge sort.
It's a perfect example.
We break the problem up into vectors of length one.
Then we merge them putting items into the appropriate order.
Divide-and-conquer.
Marge sort is merge sort.
Here's some pseudo-code.
First we have the base case
where the vector contains just one element and we return.
Otherwise, we divide the input into two parts,
and make two recursive calls,
one on the left part,
and one on the right part.
And when these recursive calls return,
we merge the results.
That's merge sort.
Now what about complexity?
Well merge sort is very efficient.
Dividing the vector is simple.
We just calculate the midpoint of a vector,
and divide it into two parts.
This takes constant time.
Big O of one.
Merging, as you have seen,
can be done in linear time.
Given n elements,
we can merge them in n steps.
That's big O of n.
But we have to account for the recursion.
Whatever time it takes to perform
division and merging at a given level,
it will take two times the amount of time it takes
to perform the same work on a vector half the size,
because we have two subvectors,
for the recursive call.
So we have this recurrence.
T of n, where T is the time
it takes to process input of n elements,
is equal to two times
the time it takes to process an element of half the size,
plus what it takes to process the current level.
Now if we solve this recurrence,
we get big O of n log n.
You'll recall that a complete binary tree of n elements
has log n levels,
and that's part of the reason why
this recurrence is solved this way.
Because as we break our problem down
into sub trees and then merge them,
we have log n levels to work with.
Is merge sort stable?
Yes.
Merge sort preserves the relative order of equal values
in the input vector.
Let's go back to that comparison table we've seen before,
now with merge sort added.
You'll see that merge sort has time complexity
of O of n log n.
But it also has space complexity of O of n
which is more than the other sort algorithms
that we've seen so far.
That's because we need that temporary vector
to hold our merge results.
It's stable and it's a divide-and-conquer algorithm.
Remember this plot from our introduction to complexity?
O of n squared
is this solid
orange curve here.
And O of n log n
is this dashed green curve.
And from this, you can see that O of n log n
grows much more slowly than O of n squared.
So merge sort is much faster
than any of the other sorting algorithms we've seen so far.
So merge sort is a recursive, divide-and-conquer algorithm.
We'll see other divide-and-conquer algorithms
in this course.
Merge sort has O of n log n time complexity.
Merge sort has O of n space complexity.
And merge sort is stable.
In the next video, we will implement merge sort in C++.
That's all for now.