- [Instructor] Hi.
Now in the previous video, we introduced merge sort.
And merge sort is a very different kind
of algorithm than we've seen before.
It's a divide and conquer algorithm
that recursively calls itself.
And in so doing, it divides the input vector
into smaller and smaller vectors,
these are the sub-problems,
and the base cases where a vector has just one element.
Now one element is already sorted.
And so where does the real work happen?
The real work happens when we merge.
We take those smaller vectors,
each one is already sorted,
and we merge them to produce another sorted vector
that's a partial solution.
And the last two vectors that we wind
up merging produce the final solution.
Now, what we're gonna do here
is we're gonna implement merge sort in C++.
I want to point out a couple of things first.
One is that it's a little wasteful
for us to keep creating new vectors.
Every time we create a new vector, there is some overhead
and memory that needs to be allocated.
And so what we're gonna do here
is rather than creating new vectors every time we divide
the vector into smaller and smaller pieces,
we're just gonna subdivide our input vector.
And that's easy to do so long
as we have a few indices indicating the start
and end of each segment.
We're also gonna create one temporary vector
for our working space.
You'll recall that a merge sort has a space complexity
of O of n,
which means we need working space equivalent
to the size of our input.
So we're gonna create a temporary vector
that's gonna hold our merged results,
and we're gonna pass that around by references needed.
And so keeping those two things in mind,
that's how we're going to implement merge sort here.
So let's get to coding merge sort.
We'll start with a new C++ file.
We'll call it merge sort.
And we're gonna need vector, obviously.
And we're gonna need iostream
so we can print things out.
And then, let's also borrow some code here.
I've got this print vector function that we've used before.
I'm just gonna copy and paste that.
And then let's start off with placeholders
for the rest of our code.
We're going to have a merge sort function.
And I think we're gonna implement this
with a separate function for merge.
Now we're going to,
and then we're also gonna have main
where we can run and test our code.
All right, so what do merge sort and merge look like?
Well, let's start with a merge sort.
It's gonna be templated.
So I'm just gonna borrow this template and code here.
And what are the inputs to merge sort?
We're going to need the input vector.
So standard vector of comparables.
And we'll call that V.
And we're gonna need our starting and ending positions.
So two indices, int, start, int, end.
And we're gonna need that temporary vector
which is also a vector of comparables.
And we'll call that temp.
So that's our signature for merge sort.
We'll get to the body in a second.
And let's flesh out the signature for merge.
So when we merge,
we're also going to have to pass in an input vector
which is also gonna be of comparables.
And we'll call that V.
But remember, here in merge, we're dealing
with a left-hand subvector and a right-hand subvector.
And so we're going to need to know where each one
of those begins and ends.
So we're gonna have to have three indices here,
int start,
int middle and int end.
And you're gonna say, "Hey, wait a minute.
That's only three."
But each subvector is going to have a starting point
and an ending point.
Well, the first subvector, the subvector
on the left is gonna run from start to middle.
The subvector on the right is gonna run
from middle plus one to end.
So we don't need to pass in four integers.
We know that the right-hand subvector
is always gonna start at middle plus one.
So we have those three,
and then we're gonna need our temporary vector
to hold our merge results.
Standard vector of comparables.
And we'll call that temp.
And so that's what merge is gonna look like,
as far as the signature goes.
So let's start to flesh these out a little bit.
Let's start with merge sort.
And you recall, this is a divide and conquer algorithm.
It's a recursive algorithm.
It's gonna call itself.
And whenever we have a recursive algorithm,
we have recursive cases and we have a base case.
We have to have at least one base case.
So we have some point where we stop our recursion.
And so the base case, as I've said before,
is when we have a one-element vector
because one element is sorted by definition.
So if
end equal start,
then we have just one element.
And we're gonna do something here.
This is our base case.
What do we do?
Well, it's already sorted.
So we're just gonna return.
And then we need to deal with all
of our other cases where end is greater than start.
Let's just make this all inclusive here.
So end less than or equal to start.
And so all of our else cases will be cases
where end is greater than start,
meaning that we have two or more elements.
So this is where our recursive cases will go.
And what do we do?
Well, we're gonna divide and conquer.
And the division is pretty simple.
All we need to do is find the middle
of our input range and subdivide.
So int middle
equal start plus end
divided by two.
Now this is integer division.
So if we're dividing an odd number,
this is gonna truncate.
If we're dividing an even number,
we don't need to truncate.
And so that gives us our middle.
And then we're gonna make two recursive calls to merge sort.
So it's gonna call itself
with V and start to middle,
sorry, middle.
So that's the first recursive call.
It's dealing with the left-hand side
which is going from start to middle.
And then we're gonna make a call to deal
with the right-hand side.
And remember, we said middle plus one
to the end.
Okay. But I've left out the temporary.
I need to pass in the temporary.
That's gonna hold our merge results.
And then we merge
with our vector.
Start,
middle,
end, simple.
So let's see what we're doing here.
We're finding, let me back up.
These are the cases where end is greater than start.
Meaning that we have two or more elements.
We find the middle so we can subdivide.
Then we make recursive calls
on the two subvectors that we get
by dividing it at the middle.
And then when we're done, we merge the results.
That's all there is to merge sort.
Now we have to deal with this function here, merge.
And you'll recall that I said merge
is at the heart of this algorithm.
And so this is where the real work is gonna be done.
So now let's complete this merge function.
We have as inputs, vector of comparables, V.
We have start, middle, and end
which indicate where the left-hand side
and the right-hand side start and end.
And we have this temporary vector that we'll use
to hold our results while we're merging.
So first, we will initialize a few variables,
int i equals start.
Now i is gonna be the index into the left half.
Int j is gonna keep one middle plus one.
That's our first position on the right-hand side,
that's the index.
And to do the right half.
And int k equals zero.
And that's an index, whoops, a temporary vector.
And we could call these left index, right index,
and temp index.
I think it's easier to work with i, j, and k,
but if you want to download the code and fiddle with it,
please feel free to change these names.
And then remember that we have a couple of cases
we need to look at.
While we have values in the left-hand side
and the right-hand that we haven't consumed,
we need to be doing some comparisons.
And then we're gonna have other cases where
we've consumed all the values on the left-hand side,
or we've consumed all the values on the right-hand side.
But let's start with the case
where we have to make comparisons.
And so, while i is less than or equal to middle,
that is, we haven't used up all of the left-hand side,
and j is less than or equal to end,
we haven't used up all the values on the right-hand side.
Then we perform a comparison.
If v sub i
less than or equal
to v sub j if the value that we're looking
at on the left-hand side is less than or equal
to the value that we see on the right-hand side,
then we're gonna use that value.
So temp k is going to take the value from v sub i.
Okay. And then we need to increment our indices.
Plus, plus K and plus, plus i.
Otherwise, else.
And in this case, we have the value on the left
is greater than the value on the right.
So we're gonna want to take the value on the right,
temp sub k gets the value on the right.
That's v sub j.
And then we increment our indices again.
Plus, plus k,
and plus, plus j this time.
Okay.
So that's when we're performing comparisons.
It would take, this case,
the value from the left,
in this case, we're gonna take the value from the right.
Okay.
Now we have to deal with the cases where we've consumed
one side or the other.
So let's look at the left-hand side first.
While i less than or equal to middle,
we still have stuff there.
Then temp k is going to get v sub i.
And then we're going to increment k to point
to the next available position in our vector
and increment i.
And all this is gonna do is it's just gonna continue
through the left-hand subvector
until it's copied all of the values
into the temporary vector.
And then we have the case while j, sorry
less than or equal to end.
We're gonna do the same thing.
Temp k is gonna take v sub j this time.
That's the value from the right-hand side.
Increment k.
Increment j.
So we're almost done.
You see, we're initializing our values here
for where our indices are,
the points of interest in the subvectors in question.
We're handling the case where we have values
on both the left and the right
and choosing the lesser
and putting it into the temporary vector.
Here, we have the cases where we've consumed
one side or the other,
and we're just continuing to consume values
from the appropriate side
and put them into our temporary vector.
And then before we finish,
we want to copy everything back to our vector v.
So for int i equals zero,
notice, this is a different i
from the one above, it's within this scope.
I less than or equal to end minus start.
Plus, plus i.
We're just gonna copy our values over.
So v start, plus i.
Remember, i could be zero.
Equal temp i.
And that'll copy our sorted values that we've built
in our temporary vector into the appropriate positions in v.
All right?
And that completes our implementation
of this merge function, which is again,
called after we get the results back
from these recursive calls to merge sort.
So I think that's our implementation.
Let's test it out.
So in order to test it out, we're gonna need a vector.
And we'll make this vector of int,
and we'll call it v.
And we'll put in some ints.
41, 13,
28,
35,
90,
34,
67,
72,
56,
30,
78,
19,
48,
20,
55,
and say 61.
Okay, now, I've put down 16 numbers here
because I want nice pretty formatting
for something I'm gonna show you a little later.
Obviously, merge sort will work
with any number.
It doesn't need to be an even number or a power of two.
So just keep that in mind.
This is just for demonstration purposes,
but we could put in any vector ints or any vector
of comparables, for example.
And we're gonna need a temporary vector, std.
Whoops, vector.
And this will also be a vector of ints,
and we'll call it temp.
And we're gonna make this vector the same size
as our data.
Okay, so now we have a temporary vector.
It's the same size as v.
And now let's call that print vector function
that I copied at the very beginning
of the video, int print v,
that'll print the unsorted vector.
And then we'll call a merge sort.
And now here, we're gonna provide it with v.
And we're gonna want to span over the entire range.
Remember, that merge sort takes a start and an end.
So this is gonna range over the entire vector.
So that's v size
minus one,
and we're gonna pass in that temporary vector too
Okay. And then when we're done, print vector v.
Now, unless I've made some typos,
that should run quite nicely.
So let's give it a run.
And we build it.
And run it.
And that's exactly what we expected to happen.
Here's our input vector 41, 13, 28, so on.
As I have up here and here is our sorted vector
in the end 13, 19, 20, 28, 30 and so on.
And that looks like it's working as it should.
Now, before we wrap up, I want to just do one more thing
to give you a little more insight into how this works
as merge sort is doing its work.
So I'm gonna create a new function here.
It will also be templated.
So I'm gonna borrow this code.
And it's just gonna print a selected range of elements
within a vector and then print a white space padding
for the rest.
So void, and we'll call this print vector segment.
And
it's gonna take a vector,
both comparables.
And we can call that v.
But it's also gonna take two integers, int start,
int end.
So that it's going to print the elements between start
and end inclusive and print white space padding
for the other positions.
So little for loop for int i equals zero.
I less than the size of the vector.
Plus, plus i.
And if
i is greater than or equal to start,
and i less than or equal, oops,
equal to end,
if it's in that range, we're gonna print the value.
And a little white space.
Otherwise, else,
we're just gonna print some white space.
All right.
And when we're all done, oops, when we're all done,
we're going to print an inline character.
I had that right.
There we go.
All right.
So now we have this function, print vector segment.
And now, where are we gonna use it?
I'm gonna go down to our merge sort algorithm.
We've calculated middle at this point,
you'll recall this is the recursive cases
and we have to calculate middle
and split our vector into subvectors.
So we're going to say print,
that's print vector segment.
V start, middle.
That's printing the left-hand side.
And then here, we will print vector segment.
The middle plus one to end.
And then after we merge again, print, vector, segment
v start, end.
And now we'll get a little more insight
into how this is working.
Let's just think about this for a second.
We're going to split some vector or subvector
into smaller pieces.
And so we're going to see the left-hand side printed first,
and the right-hand side printed second.
And then after the merge takes place,
we'll see the merge result.
But notice that these recursive calls might continue
before we get back to merging.
So let's run this and see what happens
And hopefully, there are no typos.
Yay. Okay.
So that's what I expected.
So let's just take a look here real quick.
So this is our input vector here.
And we split it and we print it.
We print this left-hand side, that's the left half.
And then we make another recursive call,
and we print the left half,
and another recursive call.
You can print the left half and another recursive call.
We print the left half.
Now this is a base case.
So there aren't gonna be any more
recursive calls after this.
This is a one element vector
or subvector as the case may be.
And so then we're gonna start processing the right-hand side
and we get 13.
And then we merge those two values into 13 and 41.
And now, this was the right-hand side.
So here's the right-hand side being split off
and the base cases of the recursion and the merge.
And then this here gets merged with this to produce this.
So 13 from the left,
28 from the right,
35 from the right,
41 from the left.
And now we process the right-hand side
because of course, these come in an order here.
And the same thing happens, we keep splitting
until we hit those base cases.
We do a merge of one element each
to make a two-element sub vector.
Do the same thing for the right hand side.
We merge those results.
And so we've completed the process here
for the left-hand subvector.
And then we do the whole thing,
same way for the right-hand subvector.
And you can see how that works.
So I hope that gives you a little more insight
into how merge sort works.
Source code is on Blackboard.
Thank you very much.