Hi, everyone.
So in this video, we are going to discuss another sorting algorithm, so much art, so much orders
and the sorting algorithm, but it uses recursion so much as a recursive algorithm.
And my thought is basically very, very fast.
So it's a very fast sorting algorithm, so since it's a recursive algorithm, so let's discuss about
the base case.
So basically, it's a very simple.
I want to show tonight.
And if the length of the original so if the length of the zero, that means my area is empty or the
length of the ad is one.
So zero or one if the length of zero zero elements or one element I can say my area sorted so I will
not do anything and I will return.
So now let's talk about the recursive case.
So we will be given an array and I want to sort this area.
So I want to apply my algorithm on this area so that this area can be sorted.
So what do we lose?
Our first step is basically we will divide that into two parts.
So this is start.
This is end.
And this is so divided into two parts.
Let's say the name of this area is E!
So this will be my first study and this will be my secondary.
So we'll divide the area into half.
OK, so divided into two parts of equal size.
So let's say the name of this area is X and the name of Dissatisfy.
So if the elements are five four, two, five four, two will come here.
And if the elements here are legit, three, seven and one, two, three, seven one will come here.
So first step is very simple.
You will divide that into two have the second step is basically apply my thought on this area.
I apply my thought on this area.
So it is the property of my.
So given an area majority will sort that.
So this area will get sorted.
This area will get sorted.
So it will become two, four, five.
So this is your area.
And similarly, this idea will get sorted.
So it will become one, three and seven.
OK, we are applying my apply my chart on Adebiyi.
And similarly, I blame my thought on that.
What is the meaning of applying what I blame on Sarbanes called preclusion?
So it's a recursive algorithm.
It's recursive algorithm, so called equation decided this will get sorted.
I will call this area.
So this idea will get sorted.
So after applying them, I thought after calling litigation.
So now we have to sort it out is we have to sort it out is and what do we need to do?
We need to merge, sort it out.
So this is area.
So we need to merge those already into Arrietty.
So much to sort of that is much, much closer to that X and Y and to Arrietty.
So if you will merge these two areas, your area will become one to.
Then three, four, five and seven, so your array will be sorted, your area will become sorted.
OK, so this was your original area.
Now this area has been sorted, so I hope you understood the algorithm.
So let me explain you that algorithm one more time.
So the first step is basically first step is the arena to have to break into two equal parts?
You will break that into two equal parts.
Second step is basically called oxygen on board the half colocation or you can say apply mudguard on
board of.
I blame Mozart on board the half, and the third step is basically to apply Mozart on both part and
the third step is very simple, much to sort of that is.
So now you will manage to sort it out is.
Simple, so let me explain them one more time, so this is your Urara.
Let's say the name of this ad is a this is your area, what you will do, you will break that into two
parts.
So let's call this part as X..
So this is my X.
And this is my area, so these elements are present in that area.
So now what will do?
Apply my collocation on this area?
I apply my collocation on this area.
So this area is now sorted.
This area will be sorted and this area will be sorted.
Now we have to sort it out.
So this is a sort of that this is a sorted out.
So now we have to sort it out is and what we will do now, we will merge the two sides.
That is, we will merge the two sorted areas in another area.
So in area, we will merge the two sorted out X and Y and finally our area, it will be as area.
So that is how the merger algorithm works.
So this is the working of my algorithm.
So let's take one example so that you guys can understand it better.
So, for example, if I want to start this at 71 and five, six and two, I want to sort this area.
So this is my area.
Now what I will do so I will break that into two parts.
So we need to divide this arena to half.
So this is 71, the first part of 71.
Second part is five six to.
So divided into two have since elements.
So one side, two elements and the other side only one element.
Similarly, one side, two elements, and in the other side, only one element.
So now the elements are even so one in one, seven and three, so this is only one element.
And what was the best case?
So best case, if you remember, if the element is one.
So if the length is one, adelante is one, that means if only one element is there, then that element
is already sorted.
So basically, this is a sorted area because there is only one element, so do nothing.
So here this will be five and six.
We are breaking the array into two parts and this is only one element.
So do nothing.
So you have two areas, you have two areas and both that it has ordered.
So one element sorted out, one element be sorted out.
So you have two areas to sort of that is and the third step mother to sort it.
That is so much to sort of daddy.
So it will become two seven master sort it out.
So we have one area, we have another area and board that is all sorted.
So if you will merge them, this will be a new area.
One three seven.
So this is a sort that this is just after daddy.
Now let's merge them.
So after merging, it will be five and six.
So this is a Saturday, this is a Saturday.
Now let's merge them.
So after merging, it will become two, five and six.
So now we have a at Eddie.
We have this hour today, let's march the truth out today, so we have finally will be one, then two,
three, five, six and seven.
So this will be your Saturday today and this will be your final at 8:00.
So this was the original.
This is the sort of that is so now the elements are started.
OK, so I hope you understood the working, so can you write the code?
Writing the code will be very simple.
What we will do so I am only discussing the approach.
You will write the code yourself.
So there are two ways of writing the code.
So what you can do, so let's talk about option one.
So option one is basically this is the area which I want to sort, this is at a this is necessity starting
next.
This is the end index.
So first step, break this down into two parts.
So what you can do, you can create another area.
Let's name it X, you can create another area.
Let's name Midway.
So you will copy all these elements here and that X and you will copy all these elements in it if I
copy all the elements in Adibi.
So now what will look, we will apply a much sought on Addicks, we will apply a chart on Adivasi.
So now I have Addicks.
Which is a sort of that I have anyway, which is a sort of daddy and I have Eddie.
I have this every so now you will merge these two sort of daddies, so this is option one.
Option two of solving the problem can be.
So option two is basically this is the area which I want to sort.
So first step is same, you will break the urethra, you will divide that into two parts.
Now, I will not create another X and Y.
What I will do, I will just apply them on this undercity.
I will treat this small area as if it is an independent area, so I will apply my chart on this area.
Similarly, what I will do, I will treat this small area as if it is independent area.
So I will apply my chart on this area.
So I'm not creating new areas.
I am not creating new areas.
I am just considering this area as if it is an independent area.
So I am certain this area apply on this area.
So now this area has been sorted, this area has been sorted and ready to do so.
You need to merge these two sorted areas.
You need to merge these two, sorted that into itself.
So this is area and you need to merge.
This is also already.
So you will merge.
You will write the code in such a fashion that these two areas, these two sorted areas after merging
will become completely sorted.
So which option is better?
So this option, option two is better because we are not creating new areas, but both options are right.
OK, so both options will work.
Both are 100 percent right.
You can use any one of them.
So what do your code will look like?
So I'm just writing only the functions you need to compute those function so that they will be void
because I'm going to do the changes in the area itself because they are passed by my the name of the
function is from my chart, so I will take it as input.
I will take what is the starting next.
What is the an index.
And you will write the code, so I am writing a little biscuits, so biscuits will be left to zero to
start rather than end means lanta zero and start to constraint means Lenthall one.
So in that case, you do not need to do anything.
You will return.
So what is our best case, best guesses if Lanta zero?
So to zero means start good and end all anyone.
So if there is zero element or one element, so when means start a cause.
And so this is a condition for one element.
This is a condition for zero element.
And our base case was if the length is zero or the length is one zero elements of an element so that
it will be sorted, so do nothing.
And this is handling both cases.
OK, so both the cases will be handled with the help of this condition.
So now you're ready.
You are basically ready.
What you will do now this is already.
So let's apply option one.
You can use option two also.
But for making the problem easy, let's use option one.
So we will use option one.
So what you will do, you know, the starting next you know, the end of next.
Can you find out?
So after finding out the body will do, you will create another area X, you will copy these elements
you will create and right away you will copy these elements.
So now you have Erich's.
You have anyway, so the starting next is S and the ending index is.
So this will be made plus one and this will be.
And so what you will do, you will call that.
It goes in my chart on that X starting next start and then similarly you will call the onorevoli starting
indexes murder plus one and index is.
And so this will be sorted and this will be sorted.
So now we have to sort that is and we need to merge them.
So we need to merge to sort.
That is so far that what we will do, I will write another function void merge.
Let's say the name of the function is merge Adi.
So Void Margera it is it will take X.
I want to merge X and ATV into Arrietty and I will take what is this starting index and what is the
end index.
And they need to write the function to complete this function.
OK, so you have an X which is sorted after applying dedication, after applying dedication.
This is also this is this will also get sorted.
And now what you need to do, you will call this function, Marjorie, you will pass at X, you will
pass Ariva Buyside X, but anyway, you will pass this area, it will pass the array, it will pass
this starting next and the next.
This is the starting next.
This is the index.
And you will write the code for this function.
Much to sort of that is so your edit it will be sorted.
Simple.
So what you need to do, just write the code for this Margery's function and write the code for this
function.
I hope you can do this because we have done many problems of recursion, so I hope you will be able
to do it properly.
So this is it from this video in the next we do, I will write the code for the Mod, so I will see
you in the next one.
Thank you.
Bye bye.