Hi everyone, let's do this question.
You are given an array of integers.
Write a function that will take this array as input and return the sorted array using merge sort.
So we are asked to sort a given array of integers using merge sort.
So if this is the given array, then we have to sort it and the output would be 12357.
And we have to do this using merge sort which is a very famous sort.
Now let's go ahead and discuss merge sort in depth in this video.
Now merge sort is a divide and conquer algorithm.
With this we mean that we divide the given problem into subproblems and then we solve the subproblems,
which in turn helps us to solve the given problem.
So that's how a divide and conquer algorithm works.
Now with respect to merge sort, the divide part is that we keep dividing the given array till it is
of size one, and we use the property that an array of size one is already sorted.
Right.
Because you just have one element.
So it's it has to be sorted.
So for example if you have an array and it has just one element let's say five, this array over here
is already sorted.
So this property is used by merge sort.
All right.
And when it comes to the concre part we merge the sorted arrays.
Right.
So over here we have the array sorted and we merge them.
We merge the sorted arrays.
So we have let's say we have two arrays of size one.
Let's say we have five and four.
Now we merge them and we get four comma five because we merge the sorted arrays.
And this keeps happening even when the size is no longer one.
Now over here for example, the size is two.
And let's say we have another array with two size.
Now this these two will be sorted already and then we merge them up.
So that's the concre part of the merge sort.
So merge sort is a divide and conquer algorithm.
And we do decomposition or we divide the array and then we sort the array upwards.
Now we will also look at in this video the complexity analysis of an algorithm to merge two sorted arrays.
Because we will be using that in merge sort.
And finally at the end of this section we will discuss that merge sort is a stable sort algorithm.
We will discuss the meaning of this.
We will discuss what is a stable sort algorithm and what is not a stable sort algorithm.
All right.
So let's get started.
And first we will look at the algorithm to merge two sorted arrays because we will use this in the merge
sort.
All right.
Now let's try to understand the logic behind this.
Let's say we have two sorted arrays 257.
This is sorted and 146 this is sorted.
Now remember when we say that we have two sorted arrays, both of them should be either ascending or
both of them should be descending.
It's not that one is ascending and one is descending.
Now in this case, let's take the case where both of them are ascending and we want to merge them.
And the merged array should also be ascending.
So what do we do.
Let's have two pointers.
All right.
So two pointers will point at the beginning of these two arrays.
Now we will compare these two and which is smaller among two and one.
We can see that one is smaller.
So let's fill that as the first element of the result array.
All right.
So this is the result array.
So the smaller among these has to be the smallest right.
Because this is the smallest among all of these.
Right.
And this is the smallest among all of these.
So the smaller among these two has to be the smallest among all the elements.
Right.
So by just comparing two and one we see that one is the smallest.
And we fill it over here.
Now we have used up this one over here.
So let's move the pointer ahead.
All right.
Now let's compare the elements at the pointers which is two and four.
So we're going to compare these two.
Let me just clear this up.
Now we are just going to compare two and four.
Right.
So which among these two is the smallest.
The smallest is two right.
So we fill that over here and we have used up two.
So we move the pointer ahead.
And we keep doing this again and again.
Right now we compare five and four.
And the smallest among these two is four.
So we fill four and we move the pointer ahead.
And we compare five and six.
The smallest among these two is five.
So we fill that and we move the pointer over here.
Now we compare seven and six.
The smallest among these two is six.
So we fill that over here.
And then we are just left with seven which we fill over here.
And we get the merged array.
And this array is also sorted.
Now we can see that the time complexity of an algorithm to merge two sorted arrays is t of is is O order
of n plus m, where n is the size of one array and m is the size of the other array.
Why is that?
So we can see that we have to visit each item once right.
So that's n plus m operations.
So the time complexity of this algorithm that is to merge two sorted arrays is order of n plus m.
All right.
What about the space complexity.
We can see that we made a new array over here right.
This is a new array.
And the size of this array is n plus m right.
Where n is the size of one array and m is the size of the other array.
So we can say that the space complexity of this algorithm is also O of n plus m.
All right.
So that's done.
So we have looked at the algorithm to merge two sorted arrays.
And we have looked at the time complexity and space complexity of this type of an algorithm.
Now in this case the size of these two arrays was the same.
So let's also quickly look at the case like what should have been done if it was not the same.
Like for example, if there were extra elements over here, like let's say we have eight and nine also
over here.
So we are trying to sort we are trying to merge these two sorted arrays.
Right.
So this is also sorted.
This is also sorted.
Now we would have proceed as we discussed over here.
And we will reach this stage right where the pointers at this point are over here and over here.
And these elements are sorted.
Now we see that we are left with these elements over here.
And we just pick them and put them at the end over here.
Why is that so.
Because we know that this is the the greatest element at the current moment in the new array.
Right.
And these are anyway greater than these because this array over here is also sorted.
So we just pick them and put them.
And at the end over here and we have our result.
All right.
So we have seen that to merge two sorted arrays, we have seen the logic of how we can go about it.
And we have seen that that algorithm is of order n plus m space and time.
Now let's proceed with the merge sort.
All right.
Now for this, let's take an example.
Let's say we have to sort this array.
This is the input array.
And let me write the indices over here 012345 and six.
All right.
Now what we will do is we will break this array into two halves.
All right.
So let's break it into two halves.
And we have two sub arrays.
Right.
So let's call this the left side.
And this is the right side.
Now what we will do is we will again call the merge sort function on this left part right.
So let's break this down.
So this becomes seven three and eight five.
So this is broken into two.
Again we divide this 173 into two sub arrays of one length one right size one.
So basically we are keeping on dividing till we reach arrays of size one.
And we know that an array of size one is already sorted.
So we are using this property.
So an array of size one is already sorted.
So by dividing the given array again and again till we reach an array of size one we have achieved two
sorted arrays.
Now these two arrays are sorted right.
So these two are sorted.
Now we will use the function that we discussed previously which can merge two sorted arrays.
Right.
So we will use that function to merge these two together.
All right.
So let's see that.
So we have these two arrays which are of size one.
And they are sorted.
So we call our function which we discussed before.
And this is now merged into this array over here.
Right.
So three comma seven.
So let's replace that and let's replace this with three comma seven.
All right.
Now what we do is we we got this back right.
We we went further and it was broken into arrays of size one.
And then it was merged and we got it back.
Right.
So we came back over here after this it will process the right side.
Right.
The the function will process the right side.
So what we are doing is we are recursively calling the merge sort function first on the left side then
on the right side.
So because we got the return from the left side, now we call it on the right side.
So this is also broken into two arrays of size one.
So again these two are now sorted because array of size one is sorted.
Now we call our merge function.
And we merge these two together right.
So we get five comma eight.
So let's replace this with five comma eight.
So these two are now sorted right.
So these two came back.
So this will now sort and we change this one over here.
Right.
So we call our sort function our merge function to merge these two together.
So merge them and we get three comma five comma seven comma eight.
And we have already discussed how that is done before.
Right.
So let's replace that over here.
And we get this array over here.
Now because it's done for the left side it is done right.
So it moves to the right side.
So notice first it does the left.
Now again you can also do first right.
But let's say we either one has to do first right.
So let's say we are doing left first.
So it will keep doing left till that is done till it returns from there.
Then it will do right.
So this is done now.
So now it will start processing the right side over here.
It will break this into two arrays.
All right.
Now this is already of size one.
But again let's say it's doing left first.
So it will break this again further down to one and nine.
So these are two arrays of size one.
And these two are sorted already.
Right.
So we will call our function to merge two sorted arrays.
And we will get one comma nine.
So let's replace this with what we get over here.
And we have one comma nine and five.
Right.
And then this is already of size one.
So this is already sorted.
Now we merge these two together and we get one comma five comma nine.
And we replace this with what we got over here.
So these two are now sorted.
Now we call the function again to merge two sorted arrays.
And these are merged.
And we have our answer.
This is now sorted.
So this is how Merge Sort works.
Now let's quickly take a overview of all the steps that we did.
Right.
We went from here to here.
It called the left first.
Then it went over here.
It went over here.
Now this was sorted right.
So again uh, over here, I've just written it in such a manner that we can visualize all the divide
together.
So all of this is divide.
And then then we had the concre part, which is the merging part.
Again, it's not going in this order.
We have discussed the order.
So after this it will merge these two together.
It will return over here right.
Then it will process this.
It will merge them.
This will be returned and then this right.
We have these two together.
We have these sorted.
So then it will sort this.
So and the left part will be done.
Similarly it will process the right part.
So we have this is the process by which the merge sort functions.
All right.
Now let's look at the complexity analysis of the merge sort.