In the previous lectures, we have talked about selection sort and bubble sort, two of the easier sort
methods that we can we can learn about.
So now we're going to up the difficulty a little bit and begin talking about merge sort.
And merge sort is an algorithm that is considered to be an example of dividing and conquering.
So this algorithm, what we're going to do is initially divide the array into two equal halves, and
then they are combined in a sorted manner.
Right?
So we're going to divide and conquer and then re merge them back together into a sorted final array.
So let's take a look at what that means.
So a very high level view.
We'll say that we have an array of four seven.
Three, five.
One and two.
So this is our initial array right here.
So we have our all of our elements, and we know that this is going to be a divide and conquer.
So we will say we're going to divide right here at the midpoint.
So divide the array and a half.
So now we have two arrays, four, seven, three.
And five.
One, two.
So again, this is very high level and then we will go over a little bit more in depth after we get
this high level view and.
Out the way.
So now we have divided our initial array and now we want to conquer in a way aka sorted, and then we
want to merge it back together.
So now we're going to sort it.
So three, four, seven, and then one, two, five.
Again, these are their own arrays.
And now that we know that these have been sorted, we want to merge it back together.
So one, two, three, four, five, seven.
So now we have merged them back together and we just executed.
Merge sort.
So how can we eloquently kind of evaluate how this works?
Well, we're going to have a couple of things that we need to do.
So with this being if you might have kind of saw it.
This is actually going to be a recursive algorithm because we're going to continuously divide and conquer.
So we will continuously call on one of our functions in order to continuously break down our array until
we have a very basic one, maybe two element array that we can very quickly sort and then start unwinding
the stack and merging everything back together.
So we're going to have a base case where the array length.
Loop.
The array length is equal to zero or one.
And then the steps that we want to do is we want to break the array in half.
Call.
Merge sort.
On both halves.
And then lastly, the most important part.
We want to merge the two sorted arrays.
Okay, So now let's look back at our initial example because we want to see how this works, obviously,
throughout the entire the entire process.
So let's give let's give ourselves some additional space down here and let's leave our base case and
everything.
That way we can kind of see what we're working with.
So our array
was what was what did we have?
473512.
So we want to sort 473512.
So I went ahead and kind of split it up because we already know that that's what we're going to need
to do.
So we have our two arrays right here.
Well, what we're going to want to do here is split this array up.
So our midpoint is going to be this seven.
So what we'll do is we'll create an array with four and seven, and then we'll have a three here.
Well, obviously three is sorted because that is its own array with one element.
So that satisfies our base case.
But four and seven, we can split it up even more.
We can split it up into four and seven.
So now we know that four and seven are sorted and our base case is satisfied.
So we can also begin working on this one.
So we will have five and one and then two.
Obviously two was sorted and now we will have an array of five and one here as well.
So we now have a total of six arrays technically of four, seven, three, five, one and two.
And now that we.
Have called Merge.
Sort on everything.
We want to begin merging all of our sorted arrays.
So down here we know that four and seven.
So up as we unwind our sorted array here is going to be four and seven.
And now we're at the level where we have the three.
So we're going to merge the three back in.
So now we know that we're going to have three, four and seven, and that's going to be our final array
there.
Over here we're going to have one and five and now we need to sort in the two.
So up here, we're going to go 1 to 5.
So now we have our last two arrays that need to be sorted and they will obviously sort to one, two,
three, four, five and seven.
So as you can see, the complexity of this algorithm is a little bit more difficult than our previous
two in bubble sort and selection sort.
But hopefully you have a good understanding of how this is going to work.
And now we will begin implementing this algorithm in the next lecture.