So, now we have, we have described the algorithm merge sort, and
again we illustrated it on this list.
When we took the list, we kept dividing it until we got to the leaves.
For each one of them, there was nothing to do, they were already sorted.
We go up and do the merge.
As I be when I, when I began describing the algorithm, or
before we start describing the algorithm,
I said we are going to go into an o of n log n algorithm.
So what is the efficiency?
Well why does the efficiency of this algorithm,
why is the time complexity of this algorithm, o of n log n.
So, this is where we, we need now to analyse this.
Now, this algorithm,
notice that this algorithm is different from algorithms we have seen so far.
This algorithm is a recursive algorithm.
I say, I want to sort this list.
I don't know how to do that, I'm going to divide it into two sub-lists, and
I'm going to sort them.
So, notice that, to sort the big list, divide it into two halves, and
then sort to halves.
But I'm using the same term again.
I'm saying to sort these, to sort this big list, sort the to halves.
But this is not really sorting, because I just invoke the same word again or
the same function again and to sort this, sort the two halves and
sort each one of them, sort the two halves.
So this is what we call a recursion here, right?
I'm, I'm calling the function multiple times, but every time I'm
calling the function, I'm calling it on a smaller instance of the problem here.
So, I go sort merge sort on this list then it will do merge sort on this merge sort
on this merge sort on this is going to to do merge sort on this to in each one of
these merge sort on this is going to do merge sort on each one of them.
So, this function is merge sort is going to be called once on
this its going to be called once on this once on this its going to be called here,
here, here, here.
It's going to be called again on each one of these.
So it's going to be called many times.
At the end when it is called here, when I say merge sort of this list,
it will look at the list say okay, it has one item, done, it is sorted.
And then after that, the merge comes into the picture, and
it starts doing the merging.
So no more sorting now, it's just merging them.
Right?
So what is the running time?
And here, but since this is a recursive algorithm, we do, the technique for
analysing the running time of such an algorithm, is a bit different now, right?
So I am doing [COUGH] let's look at it is that,
when we are doing merge sort, [SOUND] of a list.
Of n items, let's say for example, ni,
it has n items from position zero to n minus 1.
What merge sort is going to be doing, it is going to be doing three things.
It's going to be doing merge sort on L.
And the first half.