Hello all and welcome back to this video.
So in this video we are going to continue our discussion on recursion.
And now start with sorting algorithm which we can do using recursion.
So as of now of course we have seen multiple sorting algorithms like bubble sort, insertion sort and
selection sort and have done them iteratively as well.
Now in merge sort, it's actually a recursive sorting algorithm and it is normally very fast.
Now why it is fast?
We are of course going to see in the upcoming modules when I'm going to teach you about time and space
complexity.
But in this specific video I'm going to teach you the intuition behind Merge Sort give you a skeleton
code where I would like you to try because now you know recursion properly like we have done lots of
questions.
I have told how to handle arrays as well with recursion.
I would like you to try and code the merge sort algorithm.
Okay, so let's get started.
Cool.
So everyone, uh, let us understand the basic intuition behind merge sort.
Uh, it is actually based on recursion.
So always remember the types on how we can break our problem in an array.
Right?
The one which I taught you.
So the problem is going to be like this only we are going to get a list.
We are going to get a list.
And we have to make sure that we sort this list out.
That is from increasing order, from starting to end right now.
The idea which I apply to this particular problem is to break down this problem, or rather I would
say is I can divide this particular list, right?
I can divide this particular list.
And now let me make two parts.
So this again is a very common thing to do.
We are just dividing our list and breaking it into two parts.
So this can let say my left part and this can be my right part.
Now if you see, I have actually broken my list from a one big list to two small list, and I want to
sort these two individual list.
Right.
So a perfect use case of recursion.
We have actually broken down our problem and made a same problem with a smaller size.
Now what I can do is I can call merge sort on this left, and I can call my merge sort on this right.
And I can be assured that my arrays are going to get sorted.
The reason for that is of course we don't question the induction hypothesis.
Okay.
So I'm going to call merge sort on these individual halves.
And I can now be sure that my left and right half are going to get sorted.
Okay.
Next.
What all I have to do now is just to make sure that I am able to.
So I am now I now have two sorted lists left and right.
And I need to make a third list which is having all the elements, which is having all the elements
of these list, right, which is having all the elements of left and right, but in sorted order.
Now the problem might seem a little familiar, right?
Because we have already done this.
You have already done this problem.
When I was teaching you about list where I gave you an L1 and L2 and you have to return me an L3 list
three, which is having all the elements of L1 and L2 in a sorted manner.
Right.
So that's actually the whole idea or the whole process behind merge sort.
So we are dividing and conquering our list here right.
So we have divided our list and then we are trying to conquer it.
We asked individual half to go and get sorted with the help of merge sort.
And that will happen.
And we just have to now make sure that we are merging the same properly.
Okay, so let us see the same in code as well.
How the skeleton will look like.
So the first thing is we are going to make a merge sort L1 right.
We are going to get a list.
Let us pass as of now.
Okay.
So pay attention everyone.
Now let me explain you this intuitively as well.
How the same will roll out intuitively so that you always remember.
Now the very first thing which you have to understand.
It is of course because this algorithm and fast as compared to other sorting algorithm which we have
studied and we are going to see that now let us think the same intuitively as well.
So let me explain you this using again the example of students in an assembly which we have already
seen, and learn our other sorting algorithm like that.
Right.
So you will be able to connect the dots and always remember the same.
That is my aim that intuition based things actually remain with us.
So I will try that using this example.
You always actually remember like other sorting algorithm on what merge sort is.
Now as a teacher again we are taking the same use case as a teacher.
We have these eight students right.
And I have to sort them.
So they are standing in an assembly.
I need to make sure that they are in increasing order of their height.
The way it used to happen in schools or colleges right now, my understanding is that instead of working
on these eight students altogether, what I can do, what I can do, is I can ask and divide this particular
into half.
Now, I can, of course, ask the first half and the second half to get sorted.
So I have broken down my problem from 8 to 4 and then I'm going to merge it.
Right.
Now let us go a little bit deep down okay.
To understand what exactly is going to happen at each step.
Let's say once I'm going to divide it.
Once I'm going to divide it.
Then we are going to actually get two of such groups.
Right.
We are going to get two of such groups.
And let me just draw a line in the middle as well, so that it is clear that this groups are separated,
right?
So these two groups are separated.
Now again what I'm going to do.
So let me just keep on drawing these walls between them so that you don't get confused.
All I am doing is I have now separated these two groups.
Okay?
Now again, I am just dividing it.
Right?
So this is what recursion is, right?
We keep on breaking down the problem.
Now again you don't have to think of this while writing the code.
But for the holistic understanding, I want to make sure that you understand how it's going to roll
out.
Now this again is going to get broken from half and we are going to get two groups again.
Now group of two two students each is again going to get broken.
Right.
So we are still dividing them into half.
Let me create a wall between them.
So you do not get confused right.
And now if you will see what we have actually arrived at is that we have a single single student.
Right?
Single single student.
So from a group of four, I have actually kind of divided them out.
Now the basic idea is to merge them on because a single student write a single element is always sorted.
You cannot sort more of, I would say a single element in a list.
If we are getting, let's say five, then this is a kind of a base case, right?
This is kind of base case where we cannot do more sorting on top of this.
So now next part which I have to do is merge them.
And while merging I have to make sure that I now sort them in ascending order.
So when I'm going to merge them, when I'm going to merge them, this is exactly what's going to happen.
First, this half like these two are going to get merged.
Two is smaller.
So it's going to come in starting and four is going to follow.
Similarly here three is smaller.
So three and seven okay.
So we have these two lists which are sorted.
Now going to the next part I'm going to sort these two okay.
So at every step I am just solving the same problem okay.
And that's actually what recursion is.
Now of course the way I have taught you, you don't have to think about them.
But you should have an idea that, okay, exactly how the steps are rolling out so that you can actually
make a recursion tree or visualize the same when you are doing or solving the problem.
Okay, now because I have these two groups, finally I am going to merge them.
Finally I am going to merge them into one group.
So now two is the smallest going to come first.
But now next I am going to merge them.
Three is the next one right.
So three is going to come here, three is going to come here, four going to go here and seven.
So now if you will see this is one sorted group right.
This is one sorted group.
In a similar manner in a very similar manner I am going to get another group okay.
Which is the these 1658.
This is also going to get sorted.
And finally when I will have two groups which are sorted, two list which are sorted, all I have to
do is just apply my merge function again correctly and I will be all good.
Right?
So I hope with this example, with this intuitive example and walk through the overall idea about merge
sort is a lot clear.
I am not on the right side.
I want you to actually draw the same.
That's why I kept it empty.
Okay, but I hope you get the idea.
The intuition that is very, very important.
Okay.
Because based on that, only you will be able to write the code.
Now, let me help you to find the skeleton or actually write the skeleton code for the same as well.
In the initial of course, we will be having a list.
Okay.
So let's call it L1.
Now my whole aim is to make sure that I am able to divide my problem.
So let's the way I'm going to divide it is going to be actually I'm going to find my medium.
We have already seen how we can find the medium right.
One thing to note this time again as well, we are actually going to work with start and end.
So this has already been covered.
This approach has already been covered in the binary search in the last video.
So please make sure you see that I explained to you how arrays problem we divide using these pointers.
Right.
So that we can actually limit the scope okay.
Now to find out the medium we know the formula.
So it is going to be like this.
And once we have find the medium all I have to do is I have to form two.
parts.
First part I can say is from S to M.
Second part maybe I can say is from M plus one to E, right.
Now these are the two parts.
These are now the individual parts.
And let me call them left and right.
Now one thing to remember here I am not going to make a slice or make a copy of that.
That also I've taught you already that that will unnecessarily, unnecessarily basically increase the
size or the space.
So I'm going to just refer to them using the these indexes only.
Start medium and end.
Okay.
Now what is going to happen next is I have to call my merge sort on these individual elements.
Right.
So I have to call my merge sort on these individual elements.
And then I can assume that I'm going to get them sorted in place.
They are going to get sorted.
Okay.
So I'm not creating any new list.
I'm going to call my merge sort.
And it's going to it's not going to replace like return me anything.
It is going to do.
All the changes in this list itself, right.
Now.
Finally, all the work which I have to do is just to merge them.
So my merge function, which I'm going to write my merge function.
Okay.
It is going to take my list L one.
Take the starting position, take the middle and take the end so that it knows that okay.
Which are the two parts which are sorted.
Okay.
Again, I hope till now you are very much flexible and comfortable with this indexing of small medium.
And we have used the same in binary search and other places as well.
So please make sure that you understand this.
You could have made the copy as well left and right, but I believe that this is better overall okay,
because we are not creating any extra array in the memory array, array or list in the memory.
And of course that will be a lot better.
Now let me just write the skeleton again as well everyone based on this understanding.
So pay attention if merge sort.
So just one thing I would like to do.
Let me just change it here only.
So where I am sending the s and the starting and the end.
Okay, so let me just call this as well.
So L1.
Okay.
Let's say some 1359 ten.
Okay.
I think this is sorted only.
Just give me a minute.
Let me make it not sorted.
So just taking a normal example we might take another one while solving what should be fine.
Okay, great.
So anyways whatever is the area now I'm going to call my merge sort second.
Yeah.
Merge sort.
It's going to be L1 zero and length of L1 minus one.
So I am specifically referring to the last element.
Okay.
So make sure that you spend send this a length of L1 minus one.
Okay.
If in case your merge sort just accepts a list, then of course you can create a helper function that
we have already told you in the find indices.
Right?
So please make sure that you are aware of that as well.
We can just create a simple helper function if we just apply actually takes in a list.
And in that helper function we can send the start and the end.
Now, the very first base case, if my s is greater than or equal to E, that is, my size is one I
can just return.
I don't have to do anything right.
See, one thing you have to always remember.
I'm doing everything in L1 only.
Okay.
Next is I have to find my median.
So middle is going to be S plus e minus s right.
So this is what we have already done.
So I am finding just my middle everyone.
Now I have two parts namely the left and the right.
And I have to just call my merge sort on these parts.
How can I call that?
How can I let my merge sort know that these are the two half I can call merge sort, L1, S and m.
Similarly, I can call merge sort l1 m plus one and S and E, right.
Now once I have called, once I have called this particular 15 and 16 line, I can actually assume,
and this is something which I have taught you.
You can assume that they are going to get sorted, so you do not have to fight on that.
You will get this one 310 and this you will get as six, nine, 15.
Only.
Okay, let me make it 16, Uh, 915.
So at this point your L1 will actually be changed.
Something like this one 310 and nine 1516.
So your L1 will actually be something like this.
Now.
Yes, that would happen.
You do not have to question that.
This is something which you have actually seen a lot of time now in PMI, once this is done, all the
work which you have to now do is to just call your merge function, okay.
So you have to just call your merge function with L1, S, m and e.
So that merge function, it has an idea that okay, from where the first half is, or the left part
is from where the right half is, and you can just return.
You can just return.
And this is actually some problem which you have already done right.
So def merge l1, S, m and e.
So once I get this thing and if I write my merge function properly, something which you have already
done, your merge sort is done.
Right.
So yeah, at this point I would like you all to try this.
And in the next video I'm going to discuss the solution.
Just one thing.
Please make sure that you try to write it down.
It took me like I remember four hours to code the merge sort for the very first time.
Of course, I have not understood the same in so much depth, like I was drawing this tree and everything
and not able to understand.
Just remember one more thing as well.
There is a small caveat where I am taking this S, M and E this time.
Okay, so my list is not in terms of L1 and L2 the way you have solved this question, but I have to
make sure that I create my list either or work with this pointers of start, middle and end.
Okay, so do give it a try.
I'm pretty sure that you will be able to code it.
We have done enough recursion.
We have worked on enough list questions and if you will be able to work on that, you will actually
feel very awesome.
Now I remember even after four hours, like when I was able to finally do it, it actually felt a lot
awesome.
It's an awesome algorithm which will give us the result very fast, something which I am going to show
you in future as well.
So once you are able to code it, you will actually feel that.
Yeah, it's a great algorithm.
Okay so cool.
Then everyone let's meet in the next video where I'm going to write the solution for you.
So do give it a try and I will make sure that I explain you properly and also show you visually that
how the same can be solved.
Okay.
Thank you.