Hi everyone.
In this video let's code the merge sort together.
Now we will need a function which will take in two arrays which are sorted and which will merge those
two sorted arrays.
And the output array also will be a sorted array.
So let's call that function merge sorted arrays.
And the input for this function will be two arrays, let's call it RTÉ one and RTÉ two.
All right.
So this is one function that we will need.
And then we will need the merge sort function.
And this function also will take in an array as input.
All right.
So these are the two parts.
Let's first write this part where we take in two sorted arrays and we merge them.
And the output is also sorted.
Now let's call the final result as the merged array.
And let's say it's an empty array now.
All right.
Now we also need two pointers.
Let's call it I and J.
And we initialize them to zero.
All right.
Now, what we need to do, as we saw in the explanation video, is that we need to compare the lowest
values of the two arrays, RTÉ one and RTÉ two, and we will find the lower value and we will put that
into the merged array and then we will move the respective pointer.
So that's what we are going to do.
And this should keep happening as long as the I pointer is not is is still less than the length of the
array one, and the j pointer is still less than the length of array two, right.
As long as there are elements.
So let's write that.
So while I less than array one dot length.
And J less than.
RA2 dot length.
What will we do?
We will compare, right?
We will compare.
So if array one of I.
Less than.
Equal to.
Are two of J.
So we are comparing.
If that is the case then we will push.
Let's say we will push merged array dot push.
We will push the lower value into the merged array which is array one of I in this case.
Right now.
If we do that, then that particular element is consumed.
So we need to increment I.
Now we do the same thing for J.
So if if this is not the case.
So we write the else part.
So merged array dot push.
Will be array two of J.
Oops, I came down.
All right, so we are here.
And if this is the case we have to increment the j pointer.
So J plus plus.
Now over here it's important that you write here less than equal to right.
So why is that.
So if you just write less than and if the two values are equal right.
So it would come falsy.
And the element from array two would be put right.
But we have seen that merge sort is a stable sort.
So in case of a tie we need to maintain the initial relative order.
So we need to have less than equal to over here.
Let me quickly explain that to you over here.
Let's say we have the two arrays.
And let's say we have element four at a particular instance from array one and element four at a particular
instance from the second array array two.
Now if this was only array one of I less than array two of j, then when we are comparing four and four,
this would be falsy and it would come over here and we would push the second one.
We would push this ahead of this right then the relative order is not maintained.
So it's important that you have less than equal to over here to maintain the relative order.
Because we have seen that merge sort is a stable sort.
All right.
So let's proceed.
We have written this part.
Now all that remains is let's say we are out of this while loop.
And there are still elements.
There are still elements in array one.
So let's check that while I less than array one dot length.
If that is the case, we just need to push the elements to the merged array.
Right?
So merged array dot push.
Array, one of I.
And then we'll increment I.
So as long as there are still elements in I, we just append them to the end of the merged array.
And we do the same thing for the second array also.
So only one of these will be true.
Right.
So while j less than array two dot length.
And if that is the case, we just push those elements to the merged array.
Dot.
Push.
Array two of j and we increment j.
All right.
So we are done with this function.
And then we just need to return the result the final array.
The result which is the merged array.
So return.
Merged.
All right.
So this part of the function is done.
Now let's go ahead and write the merge function.
The merge sort function.
Now what should the merge sort function do.
First let's check whether the length of the array is less than or equal to one.
So if.
Array dot length.
Less than equal to one.
Then we just need to return the array.
Again, this is important because as we have seen in the discussion, we will keep calling recursively
the merge sort function till we reach the size of the array to be one.
Right.
And at that point we know that an array of size one is sorted.
So we will return that array.
So that would happen over here.
If the array dot length is less than equal to one we return the array.
All right.
Now if this is not the case we will just keep breaking the array into two equal halves right into two
halves.
So for that let's find the middle index.
So middle is equal to math dot floor.
And we just find we just divide the length of the array by two.
So array dot length divided by two.
So we get the middle value.
Now what do we do.
We call merge sort recursively on the left side and the right side.
So let's have two variables.
Let's call it left side and right side.
So left side is equal to we call merge sort recursively.
So merge sort and we pass part of the array.
So array dot slice.
We use the dot slice operator over here.
And we go from zero till middle right.
So dot slice.
When we do zero to middle it will go up to middle not including the middle element.
That's how the dot slice operator functions right.
So this is the left side.
And then let's call the right side as again on the right side.
Also we'll call merge sort recursively.
So merge sort array.
Dot slice.
And then we just need to pass middle right.
So if we just pass middle it will take all the values from middle till the end.
So that's the left side and the right side.
So this will keep happening recursively.
So this over here left side will keep doing until we get it back right.
Only then after we get the left side only then we will go to this line.
So the recursive functions will be maintained in the call stack.
All right.
Now once we have the left side and the right side we just need to return right.
So return.
And we have to call the merge sorted arrays function, which we have written above, and we need to
pass the two sides.
So left side.
And right side.
And we are done.
Right.
So that's that's our function.
Now let's go ahead and test this.
Let's for example write an array.
Let's say I take the array as.
537819
12.
And let's now call the merge sort on this array.
So merge sort and we will pass this array.
All right.
So let's run this and see if our code is working.
All right.
So I'm going to run this.
All right.
You can see we have one, three, five, seven, eight, nine, 12.
So yes, our code is working and we have seen how to implement implement the merge sort.
So remember we had two functions.
One is the function to merge two sorted arrays.
And the output array also is sorted.
And then we have merge sort.
And this keeps dividing and recursively calling the merge sort.
So over here we identify.
We broke the given array to left side and right side.
Right and left side is again recursively calling merge sort.
And it's passing.
It's it's it's using the dot slice operator.
So we are taking values of the array from zero till up to middle not including middle.
And then for the right side we are taking values starting from the middle till the end.
And then these are recursive calls on the merge sort.
And then we call the merge sorted arrays to.
Once we get once we get something back right in any call, when we have the left side and right side,
we call the merge sorted arrays and we merge them.
So this keeps happening and this is our merge sort.