In the previous lecture, we did an overview of what Merge sort is and how Merge sort works.
And now that we have a good understanding of how Merge sort works, we can take that knowledge and begin
implementing in our own solution.
To that algorithm.
So the first thing that I want to do is set up our logic that we're going to execute in main.
So we'll create our VEC.
And again, I want to use the same values that we used in the previous lecture.
So four, seven, three, five, one and two.
And then I want to call Merge sort and I want to pass in our VEC and then I want to print out the results
of the sorted vector.
That way we can confirm our work.
So now we can come up here and we can begin implementing in our function.
So we have merge sort and we're going to have an array and it's going to be a mutable and to mix it
up a little bit.
I want to do a slice and a slice and we can use an array slice because we technically don't need to
own the data being passed in.
We're just wanting to point to the block of memory that it is in, which is what this array slice does.
So this allows for safe and efficient access to that memory block without having to copy the data.
So at the end, I would like to return a vector.
That way we can view our results.
Once we execute our code.
So inside a merge, we want to have a base case and we want to make sure the length of our array that's
being passed in is greater than one.
That way that there's actually some work to be done.
Otherwise the array has one element and it is already sorted.
So we need to get our midpoint and for us to get our midpoint, we can just simply take the array length
and divide it by two.
And that is going to give us our midway point in our array.
And as I noted in the previous lecture, Merge sort is a recursive algorithm, which is why we went
over recursion in the previous section.
So as you know, with recursion and order for it to be recursive, you have to call the calling function
from inside itself.
So we are going to call our merge sort here.
And what we're going to do is we're going to call it on the array from the beginning of the array to
the midpoint.
So this is going to be the left half of the array.
So naturally, we need to call it on the right, half of the array.
So we'll go from mid
onwards.
So this is the right half of the array.
So now and just to get rid of all these errors, we're going to return our array as a vector.
So now that we are actually doing the divide and conquer piece, remember once we're done with the recursive
part and our stack begins to unwind, we need to merge all the elements back together in the correct
order.
So for us to do this, we're going to need an another function and I'm going to call it merge and we're
going to pass in our array and also the midpoint.
So Merge is going to be a helping function, helping function for us that's going to take our sorted
or take our divided arrays and then after they're sorted and merge them back together into one array
for us.
So we're going to have array that's being passed in.
And again, this is going to be a mutable slice, array, slice.
And then we know that we're bringing in our mid variable as well.
And this is going to be a type you size.
So let's get the left half of the array that we passed in so that we can divide it even further.
And.
That is going to be from the beginning to the mid.
We're gonna turn this into a vector.
So again, so this is left half to middle, and then we're going to say, right, it's going to go from
the mid.
Onwards.
So this is the right from excuse me, middle to the right half.
They we're going to create two variables here called L four left and R four right.
And these are going to be pretty important for us.
So we'll see what they're going to do in a second.
So now we're going to have a four loop.
This way we can begin merging our elements back in and the assort in the sorted order.
So we have for each value in the array if are are so this are here if R is equal to the right vector
length.
Or if our ll variable is less than lef dot links and left of l is less than right of R.
So what are we doing here?
So this is obviously a pretty long if check where it is an or statement.
So remember that means either this side has to be true or all of this side has to be true.
So if we are executing code in this block, so inside of this if statement, then that means R equals
the length of this vector.
Or.
The LL variable here is less than the left vector length and left.
This index is less than right of the right index.
So we're doing a lot of checking based on where our indexes are at this level.
So that would insinuate that we're going to need to update our indexes appropriately.
So what we want to do is we want to reference the valve variable and here that way we can get the raw
data in there and not some memory address.
And we want to check if that vow is equal to left at index position L.
And then we want to increment
it by one else, we're going to do the same thing.
But this time for ah, so we want to check it.
The vowel is equal to right of our.
And we want to increment it by one.
So basically what we're wanting to do is figure out if the value that we are referencing in the array
is part of the left or part of the right.
And if it is, then we want to increment that index by one.
That way we're no longer at the beginning index of that vector.
So now, once we're done with that, we actually have completed this merge sort algorithm.
Everything looks pretty good to me.
We're doing our divide and conquer phase and then we're going to begin merging everything back together.
So if we come back down here, we see that we again, earlier on in this lecture, set up this portion
of the code where we want to take our example from the previous lecture of 473512 and we want to sort
it.
So let's run this and we see down here that we have one, two, three, four, five and seven.
And that is exactly what we did in the previous lecture when we did it by hand.
So that is the correct output.
It's obviously sorted and it's in ascending order.
So hopefully you enjoyed learning how to implement a merge sort algorithm in.
If you have any questions about the implementation, please feel free to ask them in the Q&A section
and I will see you in the next lecture.