Welcome back.
So far we have discussed how the merge sort functions.
Now in this video let's look at the complexity analysis of the merge sort.
Now the time complexity of the merge sort is O of n log n.
And the space complexity of the merge sort is O of n.
Let's try to think through how we get this.
Now what does the merge sort do.
Let's say we are given an array of length n.
Now the merge sort will split it into two arrays of size n by two and n by two.
And again this array would be split into two arrays of size n by four and n by four.
And this keeps happening till we get an array of size one right.
And then we merge back.
So that's what we discussed.
Right now if you take any level for example you take this level.
You can see that we are merging n elements.
Right.
So we have seen that the algorithm where we merge two sorted arrays like merge two sorted arrays.
The time complexity for that algorithm was O of n plus m.
We have seen that right.
So for example in this level you have when we merge them.
Right.
When we merge them over here we have an array of size n by four.
And over here we have an array of size n by four.
So in this case n by two comparisons or operations will be needed here.
Also n by two operations will be needed.
So in each level that's a total of n operations because we have n elements.
You can see that right n by four plus n by four plus n by four plus n by four is a total of n elements.
So in each level n elements are merged.
The same is true for this level.
Also right n by two and n by two.
When we merge them o of n plus m is o of n by two plus n by two, which is again o of n, right.
So in each level there are n elements that are being merged.
Right.
And again all these elements are part of sorted arrays in each particular level.
So we can say that in each level we have to visit n elements and merge them.
So the time complexity is nothing but the total number of operations which will be equal to O of n into
number of levels.
Right.
Again, let me repeat in each level we have to do we have to visit n elements.
So the total number of visitations that have to be done is nothing but number of levels into n.
And that will give us our time complexity.
Right.
So time complexity is equal to O of n into number of levels.
Now let's make some space over here.
We have established that the time complexity is equal to O of n into number of levels.
Now if you consider again you could think that for dividing.
Also, why do we only consider merging even for dividing.
It's an O of n operation.
So if you consider it in that manner, in each level we are again, uh, the division is happening on
n elements.
Right.
So for the division also in each level there is an O of n operation.
So if we add that that would be n plus N2N operations on each level.
So the time complexity would be two n into number of levels O of two n into number of levels.
And because two is a constant we can just remove it.
Right.
So again we get that the time complexity of the merge sort is nothing but order of n into the number
of levels.
All right.
So we have established this.
So I've written it over here.
Now let's again look at the tree over here we have an array of size n.
It's broken into two arrays of size n by two n by two which is again broken into n by four, n by four,
etc. till we reach an array of size one.
So that's what's happening right now.
How many levels are there over here.
That's the remaining thing to be found over here, right.
The time complexity is O of N into number of levels.
And all we need to now find is the number of levels.
So let's look at the pattern over here.
Over here this is n.
This is n by two.
This is n by four etc..
And we have one over here.
Right.
So I can write n as n divided by two to the power zero.
Right.
Because two to the power zero is equal to one right.
As a side note, if you take any number like seven to the power zero, that will be 1 or 10 to the power
zero.
That's one, etc..
All right.
So that's the side note.
So I can write n as n divided by one.
And one can be written as two to the power zero.
Now why am I writing it like this.
Because over here that's the pattern.
Right over here you have n divided by two to the power one, which is n by two.
Over here you have n divided by two to the power two, which is n by four.
So every level over here is n divided by two to the power, two to the power of something.
So I can write this one also as n divided by two to the power x.
And this x will give me the number of levels which are there over here because this is level one.
So over here you can see you have one.
This is level two.
Over here you have two.
So this is level X.
And I just need to find this x.
So let's solve it.
So n divided by two to the power x is equal to one.
So let's take this to this side.
So I get n is equal to two to the power x.
Now if I take log on both sides I can get x.
Is equal to log n right.
So x is equal to log n.
Again we have seen this in the video where we discussed Big-O and logarithm.
Right.
Again let's just repeat it over here.
This is log n to the base two.
Right.
So this is x.
And as we discussed over here this gives me the number of levels.
So the number of levels in this case is equal to x which is equal to log n.
And when we say log n it's always log n to the base two.
Quick side note if you've not if you don't remember what this is let's say uh you have four.
So log four.
That's equal to two, right?
So log four is nothing but asking two to the power what is equal to four.
And we know two square is equal to four.
So this is equal to two right.
Now if you want to find log 16.
So this is nothing but asking two to the power.
What is equal to 16 right now.
Two to the power four is equal to 16.
So this is equal to log 16 is equal to four.
That's a quick side note.
All right.
So let me just erase this.
And we come back to where we were.
We have seen that x in this case is equal to log n.
And that gives us that the number of levels in this tree structure over here is equal to log n.
And we have our time complexity right.
Time complexity is equal to o of n into number of levels.
Right.
So the number of levels over here, this is level one, this is level two etc. this is level log n right.
So we can now fill in over here number of levels as log n.
So let's do that over here.
So time complexity will be o of n into log n.
And that gives us our answer.
Again quick side note let's say we have eight elements.
So how will it split.
We will have four elements four elements.
This will split into two and two and then one and one right.
So you can see we have three elements over here.
Right.
And again remember log eight is nothing but three.
So log A to the power two is 3 or 2 to the power.
What is equal to eight.
That's equal to three.
Again I'm just repeating this over here because it's difficult for many students.
So let's quickly again take the case where we have 16 elements.
Right.
Let's say we have 16 elements.
So all you need to do is two to the power.
What is equal to 16.
We know two to the power four is equal to 16.
So in this case log 16 is equal to four.
So that gives us the height right.
The depth of this tree the depth of this tree.
All right.
Now we know that time complexity is equal to O of n into number of levels.
And we found that the number of levels is equal to log n.
Therefore the time complexity of the merge sort is o of n into log n.
All right.
Now let's also look at the space complexity.
And remember the time complexity is always O of n log n, whether it's the best case or the worst case
or the average case, because in all the cases, the merge sort just keeps dividing the array into two
halves.
Right over here it's divided into halves, two halves again it's divided into two halves.
And it keeps doing that again and again.
So the time complexity is O of n log n, irrespective of whether it is the best case or the worst case
or the average case.
All right.
Now, what about the space complexity?
Now over here for this, we need to look at two things.
Right.
Are we using any extra space like creating any extra array, etc..
That's one thing that we need to look at.
And because the merge sort is a recursive algorithm, we need to look at the maximum depth of the tree
so that we can know how many function calls will be there in the call stack at any given point of time.
What is the maximum number of function calls that can be there in the call stack at any given point
of time?
So these are the two things that we need to look at when we think about the space complexity.
Now first let's look at the call stack.
So over here we can see that we have seen that the depth at any point the depth is equal to log n right.
The maximum depth is equal to log n.
That means that at any point maximum log n functions are waiting in the call stack.
All right.
So we have log n.
We have identified this log n over here.
All right.
Now the second part are we creating any new arrays.
Yes.
For example let's look at this part over here.
When we got this our sub array and this sub array sorted.
And what did we do after that.
We merged these two sorted arrays.
And we created another array of size n by two right n by four plus n by four is equal to n by two.
Again we saw that the space complexity of the algorithm to merge two sorted arrays was O of n plus m.
So in this case n and m are n by four.
So it's o of n by four plus n by four which is equal to o of n by two.
Or it's another way of saying that we are creating a new array of size n by two over here.
But after we return this up right, we no longer need it, right?
So after we return it up, we no longer need it and that memory is freed up.
Now, what happens over here?
Over here we create an array of size n right.
So that's the greatest array which we create over here.
Right.
And this is the final output.
Right.
So over here we are using space of n right.
So let's now we got the two aspects.
So over here we are using space of N right.
And over here we are using this maximum space of log n.
Again it's a constant into log n.
And over here we can say it's a constant into n but we can remove constants.
All right.
So what's the space complexity of the merge sort.
It will be log n which is this log n over here.
Plus this n over here.
Again we don't need to keep adding.
This is n by two.
This is n etc. because after we return this up we free this up right.
This is no longer needed.
So we free this space.
So at the last moment we are creating the array of size n.
So that's this n over here.
So the space complexity of the merge sort is O of log n plus n.
But because log n is less than n we can avoid this right n dominates.
Therefore we can say that the space complexity of the merge sort is o of n.
All right.
So we have seen that.
Let's quickly revise what all have we discussed so far.
We have seen that for the algorithm to merge two sorted arrays, the space and time complexity is O
of n plus m, right where n and m are the respective sizes of the two sorted arrays.
We have seen that for the merge sort, the time complexity is O of n log n, and the space complexity
is O of n.
And remember, log n is nothing but the number of levels right of the of the tree.
Right when we when merge sort keeps dividing the given array.
So log n gives us the number of levels.
All right.
And we also saw that merge sort is a divide and conquer algorithm.
And we saw that the time complexity of the merge sort is O of n log n, irrespective of whether it's
the best case, worst case or the average case.
And that's because it always divides the array into two halves, whether it's the best, worst, or
average case.
And then it takes linear time to merge those arrays.
Right.
So the time complexity of the merge sort is always o of n log n.
And as the last point, let's also consider the fact that merge sort is a stable sorting algorithm.
This is something which is very good about the merge sort.
So let's discuss this aspect.
Now.
What do we mean when we say that the merge sort is a stable sorting algorithm?
It means that when there is a tie between two elements and we are trying to sort, then the initial
relative ordering is maintained.
Let's try to understand what we mean with this.
So let's again take the example through which we walked through.
So over here you can see there are two files.
Right now they are the same value.
So whether I put this five or this five ahead in the final output the output is still sorted correctly.
Right.
But what we say over here is that merge sort is a stable sorting algorithm.
It means that the initial relative ordering is maintained.
So in the initial relative ordering this five came ahead of this five.
Right.
So over here also in the final output we will have that same order maintained.
So that is what we mean when we say that merge sort is a stable sorting algorithm.
And this is a great advantage of the merge sort.
All right.
Now let's take a quick example.
An application of this this aspect where we say that merge sort is a stable sorting algorithm.
Let's say we have four records over here and we have first name and year of birth.
So these are four people.
Now let's say initially we sort based on first name and we use merge sort.
So we get this output over here a C D and R.
Right.
And then these are always together.
So this is the satellite at this point.
Right.
So these all go together.
So we have sorted this data in this manner.
All right.
Now let's say we are applying sort on the year of birth.
So before we applied the sort this is the data.
This is how it looks right now after we apply the sort on the year of birth.
This is how the data will look like right?
We just applied sorting on year of birth.
So the smaller values are on top 1998 1998.
And then we have 2002 thousand.
Now notice that the previous arrangement is not disturbed because we used merge sort over here.
Right.
So for example what do I mean with that.
Look at the relative positions of 1998.
Previously this was the previous stage right.
This is the previous stage.
So over here Amal is ahead of Donna.
Right.
And when we called merge sort on the year of birth here still Amal is ahead of Donna.
So the previous arrangement is not disturbed.
Right.
If we were only looking at this over here, even if I swapped these still year of birth is correctly
sorted, right?
I could have written Donna first and Amal second.
Still, with respect to year of birth, the sorting is correct, but because merge sort is a stable
sorting algorithm, the previous arrangement is not disturbed or the previous relative ordering is maintained
when there is a tie.
So over here there is a tie.
Right.
So this is a great application of merge sort.
Again look at Kali and Rani over here.
Also the 2000 of Kali comes ahead of Rani because the previous arrangement is not disturbed.
Again, what are some other sorts which are stable?
Insertion sort and bubble sort is also stable and for example quicksort is not stable.