Hello all and welcome back.
So in this video let's continue our discussion on Merge Sort.
And now I'm going to code the same for you.
I hope that you have actually tried the same once at your end.
If not, I request you to try it once like it took me.
Also a lot of time.
Like I remember it took me around four hours when I did it for the first time.
Pretty sure it's going to take you a little less than that.
Okay, so now let me help you in understanding the code of the merge sort.
So we already cleared the intuition and how exactly it's going to work.
And I gave you a skeleton.
So I'm going to now complete the same only.
So that makes sure that you are able to run the same.
Right.
So now let's get started everyone.
So we have actually majorly complete the merge function because if you will see all the other functions
are already created like already done.
So merge sort helper we have is greater than E.
This is already done.
We have found the middle properly.
Not a problem.
Then we call the merge sort here.
So this is just a recursive call.
So this is the base case.
This is the recursive call.
And now we are doing our work which is the merge function okay.
So if you are able to write a merge function properly then we are sure that This whole merge sort algorithm
is going to work fabulously.
One thing here, uh, at this point, you should be a lot comfortable when I'm making these helper functions
and changing the definition of a function.
Right.
Because now we have seen lots of examples for that.
If not, I request you to please make sure that all the assignments, all the questions which I'm doing,
please make sure that you understand them properly and not just run behind solution.
Okay.
So now let me help you with whatever you want.
Uh, so I will tell you what my approach is going to be.
Let us take an example as well.
So let us say I am creating an L one which is.
Six.
One second.
Six five 1210 nine one.
Okay.
So let us say I am taking this.
Now let me discuss the approach as well because that is going to help you a lot.
Now what I am going to do majorly is one second, right?
Yeah.
So what I am going to do is everyone that we are taking this array right six, five, 12, ten, nine
and one.
So this is our array which we have to sort.
Now of course I'm going to find the middle.
Middle is going to be zero.
And this is five.
So it is going to be zero plus five -0 by two.
So it is going to be two right.
So let me just clear all this.
Let me just write it again one second.
So six five 1210 nine and one.
This is zero.
This is two and this is three and five.
Right.
So I am calling from S to M.
So this is going to be my one part.
This whole is going to be one part and the other part is going to be let me draw it in green.
Other part is going to be this.
So this is the left and right part which I am giving.
Now once I call this particular 18th and 19th line, of course I have to assume and don't question this.
We don't question the induction hypothesis that I will be getting my arrays sorted.
So this is going to be one, nine and ten right.
Now once I have them sorted, once I have them sorted, all I have to do is to make sure that I am able
to somehow create a final array where the all the elements are in a sorted manner.
So the approach I am going to follow for that is going to be something like this.
I am going to take an I and I am going to take an J.
Let's say I take this answer as a list.
It is going to be an empty list.
Of course, in the starting now I am going to compare it I and J okay.
And whichever is lower, whichever is lower, I am going to add that.
So here we can see that okay one is going to get added.
And let me move j j basically to the next step.
Similarly I will do the same.
So now I is there.
So let us move I forward again I is there.
So I now 910 and J is going to reach towards the end.
So I have to make sure that Jay works till it is less than or equal to n, right?
Because if you will see, this is going to be my start.
And this is going to be my end.
Right.
Now what I have to do now, what I have to do everyone.
So pay attention.
I have to also make sure that all the left over, like right now my eye is here, right?
So I have to make sure that all the left over variables, they are also actually adding getting added
into my list.
Now I won't be sure.
Okay, which this will make a much more sense since I coded though you have already coded using these
examples, but I am going to make sure that you know everyone is able to understand everything.
Now I have to make sure that all the list, they are properly filled.
So I have to actually write till 12 as well.
Okay, so till basically I have to make sure that I run it properly as well.
Let me help you to write the code.
So let's say first I am going to take I which is going to be equal to your s right.
Next I am taking another pointer j which is going to be equal to m plus one.
Now what I have to do is and also I have to create an answer which is going to be an empty list.
Okay.
So pay attention everyone.
So I am just like solving for the merge function.
Okay.
I do not care.
Like what exactly is happening above and beyond?
That's how I want even you to code.
Once you are given a sub problem in any coding thing, make sure that you are focusing solely on that.
Like that is something which will help you to clear interviews in each of these companies.
That is what helped me to clear my five plus Goldman interviews when I was doing the same.
Right?
Now, what I have to do while I is less than or equal to M and j is less than or equal to E, so I have
to make sure that for I, I just so see the understanding is that I have to just work on the left array
here and the right array here.
And these are the boundaries for that.
It starts from M plus one and goes till E and the left one starts from S and goes till M right.
If this is the case one second.
Yeah.
If this is the case what I have to do is I think this is the intention here.
Right.
So now what I have to do specifically, if l one of I is less than l one of J, I have to just make
sure to append this to my answer and also increase my I by one.
Similarly, if my l one of I is greater then my L one of J.
I have to make sure that this time I am appending my answer dot append l one of j, right?
So we are working on the smaller one.
We are making sure that the smaller one gets appended, right?
So this is what will happen next everyone.
And now of course for the for another use case where if.
Let us say I have a second.
Yeah.
Elif.
Okay.
So one, two.
It.
Lf l one of I equal equals l one of j.
Then what I have to do, I have to append both of them.
So in case they are equal.
And this is something which you also should make sure you handle properly.
Yes, you could have handled it in any of the above condition as well, but I like to make sure that
I'm handling everything separately if possible, because that helps you to write better code, right?
So now I have actually added everything in my answer, which is in a sorted manner.
I have added everything in my answer which is in sorted manner.
Let me do just tell me with one thing, one second.
Okay.
So indentation seems like it should be fine.
Now I actually in my answer I am having everything okay.
But still one thing is left where what if some elements of one list is left right?
So to explain you the same, to explain you the same, this loop is going to stop.
So let us say if I have one list like zero, one, two and another is like four, nine, eight.
Okay.
And I am creating my list.
So this actually is going to stop once my I reaches here where J is going to be still in the first position.
Okay.
Because I always is less than the first element in the second list.
So I'm going to add 012.
The condition the condition while I is less than m okay.
That's of course going to get violated.
So I'm going to come out of this loop.
But still I have not added everything into my final answer list.
Right.
So to make sure that I do that, I have to run the loop outside again as well.
So this is this could be easily understandable by you if you have done this problem.
When I told you to, when I asked you to do this earlier, wherein we were say like doing the same problem,
right?
To just make sure that everything in my list or sorry in the two list are added into a third list.
Right?
So now while J is less than equal to E, I am making sure that answer dot append L one of one second
l one of j and j plus equals one.
Okay.
So yeah, I think this works somehow some indentation issue is there.
But we will fix this.
That should be fine right.
So now I have everything here Okay, so now I have all the lists, all the elements which are basically
sorted in a proper one list.
Let me make it small.
Okay.
So now I have everything which is in the answer list.
I have all the elements which are in a sorted list.
Okay.
So the next step it is very important as well.
So the example I took was something six 512 right.
So the example I took was six 512 one second.
Yeah.
Six five 1210 nine and one.
So this wall is going to get sorted as this five 612.
This is going to get sorted as one 910.
And in my answer I am going to have 1569 ten, 12.
One thing to always remember and actually not forget is that this is still in my answer, and this is
not what I am looking forward to.
I have to make sure that I am actually now copying all of these back to their position in my original
N1 list.
So this was my N1 list.
I have to make sure that I copy them right for that.
Of course.
What we have to do.
Pay attention everyone.
So all I have to do is I have to take a start, right?
I have to start again from my list.
So let's say start off my answer one second.
Start off my answer.
It's going to be zero.
Start of my list or original list.
It's going to be not zero.
It's going to be s.
Okay.
So this is one major mistake which I did and spend a lot of time.
I'm going to tell you how you can also avoid these kind of things okay.
To check it out.
Now what we have to do while my start of main list start of my list is less than or equal to E, so
I'm actually traversing on each and every element all I have to do l one of start of this.
My list, which going to start from S is equals to k of start of answer, and I will just have to increment
them by one.
Right.
So I am just going to have to move them one by one.
And yeah this actually completes the algorithm right.
This completes algorithm.
So one second everyone let me see why this is all messed up.
Okay.
So something else.
Yeah.
Cool I think it works.
Should be fine.
Let us just try it out once everyone for the indentation okay.
So indentation is an issue here.
Let me see.
Okay.
Due to some reason, some, uh.
Okay.
Great.
So some indentation seems to be messed up, but should be fine.
I will check that.
Great.
So we can return as well.
Yeah.
Somehow Amerindian has changed to three, which should be fine.
Now if I run it.
Okay, so I am not printing L1 and I am not calling even this.
So merge sort L1, print l1.
Okay.
Name k is not defined.
Where have I used k line number 38.
Sorry.
My bad.
This is going to be answer.
Yeah.
So I'm getting list index out of range.
Let me see where I made this mistake.
We are doing J plus one.
We are doing I plus one because this was less.
This time it is greater L one right.
So we are starting J from M plus one.
That is also fine J less than E okay.
Yeah.
One mistake we have made is here now.
It should be fine okay.
So we are able to get an answer right.
This is a sorted list.
So again, I hope you understood this merge function again.
This was already written by you.
I have just the change which I have done is I have.
Now instead of sending two list, I am just sending the list a single list and this S, M and E, which
is start, middle and end.
Now let us try to understand this a little bit better.
Okay.
Let us see this.
How exactly what exactly would have gone into the code.
Now this is the example which we took, right.
The front example is what we took.
What would have actually happened.
Right.
What would have actually happened is something like this.
First in this six, five, 12 okay.
We divide it into two parts six five and 1210 nine one.
Right.
Next going further.
So always make sure that you also understand the thing which I told you in Fibonacci that we are going
to continue on left right.
So this six and this 512 would have divided.
This six of course, is a single element.
So all is good.
This 512 will further get divided.
So we are going to work on the left part first.
Right.
Because that is how function calls are getting made if you will see here.
This is where my merge spot is, right L1 S and M okay.
So this five and 12 also are the single elements.
Now six.
This is going to be in a single element.
This one gets combined is five and 12.
Now finally when we are combining both of them five six and 12.
Now of course you only have to think of this step, right?
You don't have to worry about this step please.
Follow recursion.
Don't question the induction hypothesis.
Follow the framework which I have given you in a similar manner.
Ten nine 110 is going to be an individual.
This is already sorted nine and one individually they are sorted.
When we combine them it is going to be one and nine.
Similarly, when it is going to get joined with your ten, it is going to be one, nine and ten.
And finally, when both of them combined, when both of them combine, it is going to be 12, right?
So yeah, this is something through which you can actually understand this particular code.
Now just one very good suggestion, which I will tell you is that the.
See, the reason I've told you to follow a framework is one more thing which can be very helpful to
you.
Now pay attention everyone.
So this was a list which we were working on, right?
And you have specifically written this main function.
You have written this main function.
Sorry this merge function.
Now the best thing if you actually follow the framework and do the question, I'm telling you, you
can actually now just test this function out individually as well.
So let me make it L2.
Just let me make it L2 again like this.
So it's going to be five six and 12.
And it is going to be one nine and ten.
So this is what my list is going to be right.
Once I call these things, this is how my list is going to become at this step.
Now what I can do is I can just call merge.
I can just call merge okay.
On this particular set only.
So let me just call merge.
But in my merge I'm just going to pass L2.
I'm going to pass zero I'm going to pass two and five.
So what I'm doing is I am just testing out my merge function.
I am just testing out my merge function.
Let me have to make it a little down here.
I am just testing out my merge function and on that note we can just comment everything.
Now why I am doing this?
Because I want to show you that if you follow this framework and you actually solve the problem the
way I am telling you, you can test out these functions in an interview, in a assignment, in an online
assignment, in any of the coding website, leetcode or anything.
You can just be very quick to get your answer and check if your function is working properly.
Now see, I passed it.
The thing which I would have received after calling merge sort and left and right.
But when I call this merge function finally okay, it is on this array which it will be getting.
When I call this merge function, I am able to see that it is working perfectly fine.
Now if this is working fine, then I can be more than sure that my merge sort code is also going to
work fine.
Something we have missed out?
Yeah.
Cool.
Okay, so yeah, with that, I hope this thing is a lot clear to you that exactly what is going to happen
and how you can use this way.
Like we think about recursion in actually making your code a little faster.
So instead of working on the whole code, right, you can just test out if this function is working
perfectly fine the way you want.
Now your understanding is that you are writing code for this use case, right?
You don't have to think of any of these intermediate steps.
So the thing which I want you to focus on, the thing which I want you to focus on, is just this part.
Let me click this.
Yeah.
It's just this part.
So you don't need to actually worry like how it's going to happen.
That is why I've told you the induction hypothesis technique.
Right.
And you don't have to make this tree as well.
You have to first write your code after writing your code, maybe before running it you can make the
tree.
Everything should be fine.
But once you get this five six, seven, one, 910, which I am assuming here, I would have gotten
this five, six, 12 and one 910.
And if I call this properly right, if I write my merge function properly, then I can get my answer.
Okay, so just one more thing.
I want you to show the visualization.
So this is your array six 512 110 nine one.
Let me just quickly run this.
So select the entire array.
It is getting splitted.
Then I'm going to work on the left subarray.
Right.
It's going to split again.
Uh, it's just that it is taking six five, which should be fine.
So that is just the way we calculate median.
Then again, it's going to get splitted again.
Now because this is a single element okay.
And we cannot split them an array of length one cannot be split ready for merge right.
Same for this.
They are not going to merge.
Get merged back together.
Five of course is going to come first okay.
Six is going to come next.
Okay.
Next part five 612.
We are going to merge them again.
So five is going to come first.
We know that select the smallest value on the front of each list okay.
Five is going to come first six is going to come next.
Now at this point because this list is over, we would have come out of this particular loop.
Right.
But these loops, they make sure that, you know, we are still working on each and every list.
12 is going to come now.
Okay.
Now once we have completed this left sub part, once we have completed this left sub part, that is
when this call is going to gonna be right.
So because see first you will get this six, five, 12.
It's going to call on its left.
And that is how things are going to go.
Now finally we are calling on the right part from here.
Now we are going to work on the right part similarly.
So it is going to be ten nine one.
It's going to get divided ten nine and 110 and nine going to get divided further.
Now these are single elements which are of course sorted by themselves.
Let us move forward.
Let us combine them.
It's going to be nine and ten right.
Nine and ten.
Similarly now we have nine, ten one.
So they are going to get combined again into this list.
And if you will see we are doing in place right.
Everywhere we are doing in place.
So this is going to be one nine and ten.
Okay.
And finally I think now you understand the whole row like whole approach.
The good part with the way we have learned about recursion is that this is on what we have to now work
our code on, right.
We don't have to worry about all these steps.
So all of these 68 steps, I have actually asked you to not worry about the 48 steps.
Right?
So just last step is something which you have to work on.
And let me just quickly fill it one 156 12.
Oh, sorry.
Nine, ten and 12.
And you have your issue sorted.
Okay.
So, yeah, I hope this was also a lot helpful.
This particular visualization.
So I made sure that this particular question I have visualized help you to visualize and also told you
that when faced with these questions in interview or any way or any website, how you can be smart about
debugging your code if you face an error, okay, because error will come, but you should be knowing
that how you can fix them properly.
So great everyone.
With that, I hope the merge sort algorithm now is a lot clearer.
You are very confident about writing it.
If you have not written it yourself, I will still specifically ask you to write it yourself.
Bye bye after even seeing this video.
Write it yourself.
Okay, don't see my code.
Just try to work on the understanding and you will be able to know fabulously.
Write the same.
Okay, so yeah.
Great everyone.
Now let's meet in the next class and we are going to learn another awesome algorithm using recursion
which is quicksort.
So let's meet in the next video.
Thank you everyone.