[MUSIC PLAYING]
DOUG LLOYD: OK, so a merge sort is yet another algorithm that we can use to sort out the elements of an array. But as we'll see, it's got a very fundamental difference from selection sort, bubble sort, and insertion sort that make it really pretty clever.
The basic idea behind merge sort is to sort smaller arrays and then combine those arrays together, or merge them-- hence the name-- in sorted order. The way that merge sort does this is by leveraging a tool called recursion, which is what we're going to be talking about soon, but we haven't really talked about yet.
Here's the basic idea behind merge sort. Sort the left half of the array, assuming n is greater than 1. And what I mean when I say assuming n is greater than 1 is, I think we can agree that if an array only consists of a single element, it's sorted. We don't actually need to do anything to it. We can just declare it to be sorted. It's only a single element.
So the pseudocode, again, is sort the left half of the array, then sort the right half the array, then merge the two halves together. Now, already you might be thinking, it kind of just sounds like you're putting off the-- you're not actually doing anything. You're saying sort the left half, sort the right half, but you're not telling me how you're doing it.
But remember that as long as an array is a single element, we can declare it sorted. Then we can just combine them together. And that's actually the fundamental idea behind merge sort, is to break it down so that your arrays are of size one. And then you rebuild from there.
Merge sort is definitely a complicated algorithm. And it's also a little complicated to visualize. So hopefully, the visualization that I have here will help you follow along. And I'll try my best to narrate things and proceed through this a little more slowly than the other ones just to hopefully get your head around the ideas behind merge sort.
So we have the same array as the other sorting algorithm videos if you've seen them-- a six element array. And our pseudocode code here is sort the left half, sort the right half, merge the two halves together. So let's take this very dark brick red array and sort the left half of it.
So for the time being, we're going to ignore the stuff on the right. It's there, but we're not at that step yet. We're not at sort the right half of the array. We're at sort the left half of the array. And just for the sake of being a little more clear, so I can refer to what step we're on, I'm going to switch the color of this set to orange. Now, we're still talking about the same left half of the original array. But I'm hoping that by being able to refer to the colors of various items, it'll make it a little more clear what's going on here.
OK, so now we have a three element array. How do we sort the left half of this array, which is still this step? We're trying to sort the left half of the brick red array-- the left half of which I've now colored orange.
Well, we could try and repeat this process again. So we're still in the middle of trying to sort the left half of the full array. The left half of the array, I'm just going to arbitrarily decide that the left half will be smaller than the right half, because this happens to consist of three elements.
And so I'm going to say that the left half of the left half the array is just the element five. Five, being a single element array, we know how to sort it. And so five is sorted. We're just going to declare that. It's a single element array.
So we've now sorted the left half of the left half-- or rather, we've sorted the left half of the orange. So now, in order to still complete the overall array's left half, we need to sort the right half of the orange, or this stuff. How do we do that? Well, we have a two element array. So we can sort the left half of the array, which is two. Two is a single element. So it's sorted by default. Then we can sort the right half of that portion of the array, the one. That's sort of by default.
This is now the first time we've reached a merge step. We have completed, although we're now kind of nested down-- and that's sort of the tricky thing with recursion is, you need to keep your head about where we are. So we've sort of the left half of the orange portion.
And now, we're in the middle of sorting the right half of the orange portion. And in that process, we are now about to be on the step, merge the two halves together. When we look at the two halves of the array, we see two and one. Which element is smaller? One.
Then which element is smaller? Well, it's two or nothing. So it's two. So now, just to again frame where we are in context, we have sorted the left half of the orange and the right half of the origin. I know I've changed the colors again, but that's where we were. And the reason I did this is because this process is going to keep going, iterating down. We've sorted the left half of the former orange and the right half of the former orange.
Now, we need to merge those two halves together too. That's the step we're on. So we consider all of the elements that are now green, the left half of the original array. And we merge those using the same process we did for merging two and one just a moment ago.
The left half, the smallest element on the left half is five. The smallest element on the right half is one. Which of those is smaller? One.
The smallest element on the left half is five. The smallest element on the right half is two. What's the smallest? Two. And then lastly five and nothing, we can say five.
OK, so big picture, let's take a break for a second and figure out where we are. If we started from the very beginning, we have now completed for the overall array just one step of the pseudocode code here. We have sorted the left half of the array.
Recall that the original order was five, two, one. By going through this process and nesting down and repeating, continuing to break the problem down into smaller and smaller parts, we have now completed step one of the pseudocode for the entire starting array. We have sorted its left half.
So now let's freeze there. And now let's sort the right half of the original array. And we're going to do that by going through the same iterative process of breaking things down and then merging them together.
So the left half of the red, or the left half of the right half of the original array, I'm going to say is three. Again, I'm being consistent here. If you have an odd number of elements, it doesn't really matter whether you make the left one smaller or the right one smaller.
What matters is that whenever you encounter this problem in conducting a merge, you need to be consistent. You either always need to make a left side smaller or always need to make the right side smaller. Here, I've chosen to always make the left side smaller when my array, or my sub-array, is of an odd size.
Three is a single element, and so it is sorted. We've leveraged that assumption throughout our entire process so far. So now let's sort the right half of the right half, or the right half of the red.
Again, we need to split this down. This is not a single element array. We can't declare it sorted. And so first, we're going to sort the left half.
The left half is a single element, so it's sort of by default. Then we're going to sort the right half, which is a single element. It's sorted by default. And now, we can merge those two together. Four is smaller, and then six is smaller.
Again, what have we done at this point? We've sorted the left half of the right half. Or going back to the original colors that were there, we've sorted the left half of the softer red. It was originally a dark brick red and now it's a softer red, or it was a softer red.
And then we've sorted the right half of the softer red. Now, well, they're green again, just because we're going through a process. And we have to repeat this over and over.
So now we can merge those two halves together. And that's what we do here. So the black line just divided the left half and the right half of this sort part.
We compare the smallest value on the left side of the array-- or excuse me, the smallest value of the left half to the smallest value of the right half and find that three is smaller. And now a bit of an optimization, right? There's actually nothing left on the left side.
There's nothing remaining on the left side, so we can efficiently just move-- we can declare the rest of it is actually sorted and just tack it on, because there's nothing else to compare against. And we know that the right side of the right side is sorted.
OK, so now let's freeze again and figure out where we are in the story. In the overall array, what have we accomplished? We've actually accomplish now steps one and step two. We sorted the left half, and we sorted the right half.
So now, all that remains is for us to merge those two halves together. So we compare the lowest valued element of each half of the array in turn and proceed. One is less than three, so one goes.
Two is less than three, so two goes. Three is less than 5, so three goes. Four is less than 5, so four goes. Then five is less than six, and six is all that remains.
Now, I know, that was a lot of steps. And we've left a lot of memory in our wake. And that's what those gray squares are. And it probably felt like that took a lot longer than insertion sort, bubble sort, or selection sort.
But actually, because a lot of these processes are happening at the same time-- which is something we'll, again, talk about when we talk about recursion in a future video-- this algorithm actually clearly is fundamentally different than anything we have seen before but is also significantly more efficient.
Why is that? Well, in the worst case scenario, we have to split n elements up and then recombine them. But when we recombine them, what we're doing is basically doubling the size of the smaller arrays. We have a bunch of one element arrays that we effectively combine into two element arrays. And then we take those two element arrays and combine them together into four element arrays, and so on, and so on, and so on, until we have a single n element array.
But how many doublings does it take to get to n? Think back to the phone book example. How many times do we have to tear the phone book in half, how many more times do we have to tear the phone book in half, if the size of the phone book doubled? There's just one, right?
So there's some sort of logarithmic element here. But we also still have to at least look at all of the n elements. So in the worst case scenario, merge sort runs in n log n. We have to look at all of the n elements, and we have to combine them together in log n sets of steps. In the best case scenario, the array is perfectly sorted. That's great. But based on the algorithm we have here, we still have to split and recombine. Although in this case, the recombining is kind of ineffective. It isn't needed. But we still go through the whole process anyway.
So in the best case and in the worst case, this algorithm runs in n log n time. Merge sort is definitely a bit trickier than the other main sorting algorithms we've talked about CS50 but is substantially more powerful.
And so if you ever find occasion to need it or to use it to sort a large data set, getting your head around the idea of recursion is going to be really powerful. And it's going to make your programs really much more efficient using merge sort versus anything else. I'm Doug Lloyd. This is CS50.