Let's talk about another popular sorting algorithm called Merge Sort.
The overall idea is that you split a huge array down as much as possible and
then over time build it back up doing your comparisons and
sorting at each step along the way.
The general idea of breaking up an array sorting all the parts of it and
then building it back up again is called Divide and Conquer.
Several efficient sorting algorithms have this principle at their core.
Okay, let's see how merge sort works with an example.
First we break up the array into a bunch of arrays with one element each,
now we need to start building it back up again.
You may wonder why the one leftover element goes at the beginning and
not the end.
Don't worry too much about details like that.
They’ll differ depending on the implementation.
However the step should only have arrays of size two and size one left.
First we compare these two elements to see which one is smaller.
Since one is smaller, it'll go first in our new array and
since 3 is bigger it'll go second.
Now we move on and do this with the next pair of arrays.
Again 7 is bigger than 0.
So in our new array we put 0 in the first spot and 7 in the second spot.
And now we do this one last time comparing the last two elements 10 and
2 and putting them in order in a new array.
Great that was easy enough.
Now the last thing we want to do is keep track of the number of comparisons we
did so we can come back to it when we do our efficiency calculation
overall this step took 3 comparisons each one in green.
Okay, we're running out of space, so
I'm going to clear everything off except this bottom row and move it on up.
Now we're going to combine the first two arrays and
the last two arrays and create an array of three and an array of four.
Now these comparisons are a little more complicated.
Here we're comparing an array with one element to an array with two elements.
We know that the array on the right is already sorted so
the first element of our new array is either going to come from here or
the first element of this array.
It looks like one is smaller so that will be our first element.
Now we can move on to the next element in this array and
compare it with this one.
Since 3 is smaller than 8 we'll put 3 in this box.
Now that we're done with this array we can just take anything that's left in
the other one and tack it on the end here.
Great, let's move on to building this array.
So we're going to start out comparing the first two elements of these arrays,
that's 0 and 2.
Since 0 is less than 2, 0 becomes the first element in our new array.
Okay, so now we move on to the next element in this array which is 7 and
compare that to 2.
2 is less than 7 so we put 2 in the new array.
We repeat again checking 7 against 10 and
fill them in at the end of the array accordingly.
How many comparisons did we do in the step?
Well, if you count up all the purple comparisons that leaves us with 5.
Okay we're almost there.
We just need to go through one more round to get our completely
sorted array.
This is going to start just like it did in the last round.
We start off by comparing the first two elements of the two arrays that we have,
so 1 and 0.
Since 0 is smaller it ends up going in this array and
we get rid of it in the old array.
We move on comparing 1 and 2 and end up with one being smaller.
So 1 fills in the spot.
We compare again with 2 and 3 and again with 3 and 7.
And again with 8 and 7.
And finally we're done.
We have our newly sorted array.
We need to keep track of the number of comparisons we did in this step.
So I'll write 6 comparisons off to the side here.