Welcome back.
Let's now walk through the code of the merge sort, which we have written.
Let's say that we are calling the merge sort function on this array which is 5432.
And these are the indices of the various elements zero, one, two and three.
Now what happens.
We are inside the function.
Over here.
We are checking whether the length of this array is less than equal to one, which is not the case.
The length is four.
So we come over here and we calculate middle.
Middle is equal to math dot floor array dot length by two.
Now over here the length of this array is equal to four.
So we calculate middle as four divided by two which is equal to two.
All right.
Now we go ahead to the next line.
And over here we call the merge sort function.
And we pass array dot slice zero comma middle right.
So let's write left side as LZ.
So LZ left side is equal to merge sort.
And then the array which is passed is five comma four because we are using dot slice and zero comma
two.
So it will start from the zeroth index which is this one over here up to the second index not including
it.
Right.
So that's how the dot slice uh function which is over here works.
Right.
So five comma four is passed.
And merge sort is recursively called at this point.
Now again the indices over here are zero and one.
Once we pass it right and we are again inside the merge sort function, we check whether the length
of this array is equal to one, which is not the case.
Right.
So we are over here now which is not the case.
So we come to the next line and we calculate middle.
So middle is the is array dot length divided by two.
Now array dot length is equal to two.
So two by two.
So we get middle is equal to one.
Now in the next line we again recursively call merge sort on the left side.
So we say left side is equal to merge sort.
And at this time we pass only one element right because middle is equal to one.
So we call it zero comma one.
So from zero up to one not including one.
So that's only one element.
So we pass only one element.
And at this point again we come to the merge sort function.
Right.
And we check that we see that array dot length is actually equal to one.
And hence we return this array.
So at this point the array five is returned.
All right.
And then we come to the next line right.
We call the right side.
And we only pass the element four right because middle is one at this point.
So we we we do dot slice and we pass one.
So from one which is this element, it will take all the elements which are there.
And we see that it just has only one element right.
So again we come to the merge sort and we see that the length of the array is one at this point.
So this array is returned.
All right.
So we've got the left side and the right side over here when this was the array which is passed right.
We got the left side and the right side.
And next we call merge sorted arrays.
And we pass these two arrays to the merge sorted arrays function which we have written over here.
Now let me just make some space over here.
Clean this up.
All right.
So we are over here at this point.
Now we have the merged array which is initialized as an empty array.
And we have I is equal to zero and j is equal to zero.
Now we are in this while loop I is less than array one dot length.
Array one dot length is one and array two dot length is one.
Now I is zero, j is zero, so zero less than one and zero less than one.
So this is true.
So we come inside the while loop.
Now we check whether our I that is five whether five is less than or equal to four which is not the
case.
So we come over here which is the else part.
Right.
So we check this and we come to the else part.
And we fill four over here because it's not true.
So from the else part we do merged array dot push array two of j which is four.
So that's how four comes into the merged array.
Right.
And then we come out of the while loop because now we increment j.
So j is now one and one less than one is false right.
So we come out of the while loop and then we come over here over here we we see that there are still
elements over here.
It's um this is the this is array one.
This is array two.
So there are still elements in array.
Uh one right.
So this four was taken from array two.
So there are still elements in array one right.
So we do merged array dot push array one which is equal to five.
So that five comes over here.
And then we return the merged array which is four comma five.
All right.
So we came out of this part and the left side right.
So this was a call of the left side just this right.
So we went again deeper and deeper.
And then once we got things back we are back at this point.
And we have left side is equal to this array which is four comma five.
Now we go ahead and call the right side right.
So right side will be this part.
We will give this part as input right.
So right side is merge sort.
And the input is three comma two at this which is this line over here.
Now this will again call merge sort.
Right.
This is because we have we are recursively calling merge sort.
At this point we are checking whether the length of this array is one which is not the case.
This line over here.
So we come over here we calculate middle right.
So the length over here is two.
So two by one is one.
So middle is equal to one.
And we do dot slice zero comma one.
Again this is zero and this is one.
So zero comma one will just give you one element right up to one not including one.
So we get left side at this point is merge sort of three.
And this returns three because the length of this array is equal to one.
Then we go to right side is merge sort of two.
Right.
And this again returns two because the length of this array is two.
So we come back over here and we have the left side and the right side over here.
And we call merge sorted arrays.
And we pass three and two to it.
Right.
And this again as we saw previously this merges these two arrays.
And we get back two comma three as the output array.
All right.
So we have seen that when we called this.
So we are back over here.
We called this and we went deeper.
And we came back when things started returning.
And we got this.
So left side is four comma five.
And then we came to the right side.
We went deeper and we came back when things started to return.
And now at this point right side is equal to two comma three.
Now we again call merge sorted arrays.
And we pass these two arrays to it.
All right.
Now let's look at how things pan out.
So we are over here now and these two arrays are passed to this function.
Now merged array is initialized to be an empty array I is equal to zero, j is equal to zero.
Now zero array dot one length.
This is array dot one.
The length of it is two and array dot two.
Length is also two.
So zero less than two and zero less than two.
It's true right.
So we come inside.
Now we are going to compare array one of I which is four and array two of j which is two.
Now which among these is lesser right is is it is four less than two.
No.
So we come to the else part over here, we come to the else part over here.
And we push two to the merged array.
So the merged array now has element two.
And what do we do.
We increment j.
So j is now pointing to this pointer right.
And still j is one.
And this is still true because over here I is zero zero less than two and one less than two.
It's still true.
So again we come inside this loop and we are checking array one of I which is four.
And array two of j which is three.
Right.
So again we see that four is not less than three.
So again we come to the else part and we push array two of j which is three to the merged array.
So we have three over here.
Now j is equal to two right now two less than two is false.
So we come out of this while loop and we come over here and we check whether there is, there are whether
I is less than R1 dot length which is true.
Right.
I is zero which is less than two.
Right.
So we push array one of I which is zero.
So four gets pushed over here and then I comes one becomes one and one is still less than two.
So again the next element is also pushed.
So we get four comma five over here.
And when we come over here J is already two right.
So two less than two is false.
So we don't execute this part.
And we have our merged array.
And this is returned.
So this is how the merge sort works.
So we have looked at the code we have.
We have looked at the logic behind the merge sort.
And we have analysed the time and space complexity of the merge sort.
We have coded it and we have walked through the code.
So this is what you will be expected to do in the interview.