So how many overall comparisons was that?
Well, let's try to find a pattern here.
It looks like at each step,
we did one less comparison than the array we were building.
So when we were building an array of seven, we only did six comparisons.
When we're building an array of three, we did two comparisons, an array of two,
one comparison, and an array of four, we did three comparisons.
I'm going to go ahead and
call the length of each array m just to make it a little easier for me.
So if m is the size of the array that we're building,
the number of comparisons is always going to be one less than that.
It's going to be hard to get an exact number of comparisons here.
However, we have a good friend that we can count on, approximation.
Since we know that every iteration just cycles through the same
seven elements again and again, we know that the size of our arrays,
or m, are always going to add up to seven at the end.
So again, here we have an array of seven.
Here we have an array of four and an array of three, which adds up to seven.
And here, one, two, two, and two adds up to seven.
Since we're just doing divide and
conquer, splitting up the array at each step, we can say that approximately
we're going to do seven comparisons at each step.
Again, seven is an upper bound.
We're never going to do more than seven comparisons, but
at many steps we get close to seven.
So to get the run time of a sorting algorithm, you can normally multiply
the number of overall iterations by the number of comparisons at each iteration.
In bubble sort, we were doing n comparisons and n steps.
We just proved that we're doing at most n comparisons at every step.
But how many steps overall are we doing?
Okay, so to sort an array of seven,
we had to do three steps, one, two, and three.
Also I should note some of the sub-processes that happened here.
In order to sort this array of two, we only had to do one step.
When we were sorting an array of three or
an array of four, we needed to do two steps.
We can use a nice table to keep track of all of that.
Again, so when our array size was seven, we had to do three different steps.
When our array was three or four numbers large, we had to do two steps.
When our array was two large, we had to do one step.
And if we just had one element, we don't need to do any comparisons, so no steps.
I'm going to go ahead and fill in a few numbers here just for the sake of time.
You can assume that I did these calculations on my own and
I encourage you to do them as well.
Okay, so this might look a little bit familiar to you.
Remember in binary search when we had a similar table and
the number of iterations incremented at every power of two.
Well, we actually have something pretty similar here.
Instead of incrementing at the powers of two,
this time we're incrementing one after every power of two.
[BLANK_AUDIO]
So, in the binary search video,
I proved why the number of iterations would be equal to log(n).
So if you need a refresher, you can go back there.
Again, this time is a little different because it increments
after the power of two instead of at the power of two.
Yet again, we're kind of relying on approximation here.
We don't exactly care where the change happens
as long as we capture the interval at which the change is happening.
So in summary, we're doing roughly n comparisons for log(n) steps.
That makes an overall complexity of nlog(n).
This is definitely better than the n squared we got in bubble sort.
In bubble sort, we had n times n or n squared as our efficiency.
log(n) is generally going to be less than n, but
it's definitely never going to be greater than n.
So we can say that the efficiency of merge sort is better than
the efficiency of bubble sort.
However, the space efficiency of merge sort is actually worse than bubble sort.
In bubble sort, we were sorting in place, so
we didn't need to use any extra arrays.
Here we frequently copied our values into new arrays.
You can say that the auxiliary space or the extra space we used was linear.
This complexity assumes that we got rid of arrays after we were done using them.
At each step, we were copying values into new arrays, so
we needed new arrays at some point.
However, we could say that we were getting rid of the old ones whenever we
were done.
So we're not using a ton of new arrays every time.
We really only need two different arrays at every step, the array that our
numbers were in and the new array that we're copying the values into.