Merge Sort


[MUSIC PLAYING] DOUG LLOYD: All right,
so by now we’ve talked about a couple of different
sorting algorithms that are pretty straightforward
to work with, hopefully. We’ve got bubble sort, insertion
sort, and selection sort. And what we do know is
what all of have in common is that they have a sort of worst
case scenario runtime of n squared. Can we do any better than that? Well, the answer happens
to be yes, we can, using an algorithm called merge sort. Now in merge sort, the idea
is to sort smaller arrays and then combine those arrays
together or merge them, as in the name of the algorithm
itself, in sorted order. So instead of having to think about,
we have one six-element array, let’s think instead that we
have six one-element arrays, and then let’s just recombine
them in the correct order and merge them together. That would be one way to sort it. And that’s what merge sort does. And it leverages something
called recursion, which we’ll talk about soon in another video. And if you want to get a better
understanding of how recursion works, you might want to take
a look at that video before coming and watching
this one, because this is going to talk about recursion quite a bit. Merge sort is definitely
the most complicated of the four different types of
sorts that we cover in the class. And so I’m going to go through
this one a little more slowly than the other ones. But the algorithm for merge sort
itself is actually pretty few steps. We’re basically going
to say, we’re going to sort the left half of the array,
sort the right half of the array, and then merge the two halves together. That is fundamentally what
merge sort is all about. Of course, in practice, it’s a
little more detailed than that, but let’s go through that now. So here’s the same six-element array
we’ve been sorting all the time. And we’re going to start to
follow our steps of pseudocode, which is we want to sort the left
half of this brick red array. So we’re just going to
focus on this part for now. And actually, just to make
things a little bit easier, and because I’ve colored
different things in different ways throughout this video,
we’re going to refer to this half of the array, this
left half of the overall red array, from this point forward, this
is the purple half of the array. All right? So we are now in the middle of
sorting the left half of the array. But we don’t know how to do that. We don’t know how to sort
the left half of the array. So why don’t we just go back
to our merge sort steps again? All right, well, if I don’t know how
to sort the left half of the array, I’m just going to start again. Sort the left half of this array. Now I just want to focus on this
part of the array, the left half. And I’m sort of arbitrarily
deciding that my left half is going to be smaller than my right half. I have three elements. I can’t divide it evenly. I can’t have one and 1/2
elements on each side. So as long as I’m consistent, as long
as I always choose, in this case, the left side is smaller, that will
be fine for merge sort’s purposes. So now I’m left with this
single element, this five. How do I sort a one-element array? Well, the good news here is I
actually don’t have to sort it at all. A single-element array
must necessarily be sorted. So I can say that if I’m sorting
the left half of the purple part, that is sorted. So we’re just going to call that
sorted and set it aside for now. So now I want to go back to the
right half of the purple part. That’s this. How do I sort this
array, this sub-array? Let’s just go back to our steps again. I want to sort the left half only. The left half is now two. It’s a single element. I know how to sort a single element. So I’ve sorted the left
half of this, the left half of the right half of the purple. That’s where we are. That’s sorted. Now I go back and sort the
right half of the left half of the purple, which is the one. One is a single element. It’s really easy to sort. It’s in sorted position. Now is the first time I finally get
to this third step of merge sort, where I merge the two halves together. So here, what I have to do is
consider these two light green halves. And I have to decide which
one has the lower element. In this case, it’s one. So what I do is I take
the one and I put it in the first position of
some new hypothetical array. Then I compare the two against
nothing, and I ask which one is lower. Well, two or nothing. What’s lower is two. So now let’s reframe the
picture, because if we remember talking about recursion,
we’re only focusing on the left half of the
overall brick red array, which we then called the purple array. By this point in our steps, with
respect to the purple array, we have sorted the left
half, which is five, and the right half, which
was originally two and one, but now we have done
these merging steps, and we’ve got that in the correct order. So now we are on step three
for the entire purple array, because we’ve already sort of
the purple array’s left half and the purple array’s right half. So now we need to merge
these two halves together. And just like we did a second
ago with the two and the one, we’re going to compare the
first element of the left part and the first element of the right part
and figure out which one is smaller, and make that the first
element of our new array. So I compare five and one. And I say, which one is smaller? Well, it’s one, so one
becomes the first element of this new three-element array. Now I have to make another decision. Is five lower, or is two lower? Well, two is lower. So two becomes the next
element of our merging step. Then I say, is five lower
or is nothing lower? Well, clearly, in this case, the
only option I have left is five. And so now, at this
point in the process, let’s again think recursively
about where we are. We have sorted, for the entire red
array, we have just done step one. We have sorted the left portion. We’ve done so recursively, but
we have sorted the left portion of the overall red array. So we can kind of put
this aside for now, because now we have to go to the next
step of the merge sort process, which is to sort the right
half of that red array. So let’s go over and
focus on the right half. We’re going to go through
exactly the same steps that we just went through
with the left part. But now we’re going to do it
with this red part on the right. So I want to sort the
left half of this array. Well, that’s pretty easy. I just arbitrarily again divide it. I look at it. I say, OK, well, three
is a single element. Single element is already
sorted, so I don’t have to do anything, which is great. I can just set that one aside
and say, three is already sorted. Now I want to sort the right
half of the not so brick red, but is still red, half of the
array, which is this section. How do I do this? Well, it’s more than one element. So I’m going to go back to the
beginning of my process again. I’m going to sort the
left half of that array. So I look, and I say,
here’s the left half. It’s six. It’s already sorted. Now I’m going to sort the
right half of the array. It’s four. It’s already sorted. Now I get to that
merge step again, where I have to again do these sort
of side-by-side comparisons. Which one is lower? Is six lower, or is four lower? Well, four is lower, so that
becomes the first element of our new merged little sub-array here. And then I have to choose
between six and nothing. And I say, six is the lowest remaining. So now I’ve sorted the left
half of the right half. And I’ve sorted the right
half of the right half. So now I want to merge
those two portions together. And again, we’re going to
do exactly the same process that we did for the left portion. I’m going to say, is
three lower, or is four? Well, it’s three. And then I’m going to say,
is four lower, or is nothing? There’s nothing left
on the left side, then I must know that
everything on the right has to be bigger than everything that’s
in the merged array right now. So instead of saying, OK, I’ll put
four in and then I’ll put six in, because the only thing left is
on one side, everything must go. So that all comes down. And let’s again take a second
and think about where we are. At this point, for the original
brick red array that we started with, we have gone through two
of our pseudocode steps. We’ve sort of the left half of
that overall brick red array. And we’ve sorted the right half
of that overall brick red array. And so now the final thing we have to
do is merge those two halves together. And just like before, we continue to
ask ourselves the same question again. Which is lower, one or three? Notice the little black line there
dividing the two halves to make it more visually clear. Which is lower, one or three? Well, one is. Now again I ask myself the question,
which is lower, two or three? That would be two. Which is a lower, five or three? That’s three. Five or four? It’s four. Five or six. It’s five. Six or nothing? It’s six. And so by going through
this process recursively and breaking my problem down into
smaller and smaller sub-arrays, sorting those, merging them
together, after a number of steps, I have now completed my sort. And I have everything in
order here in dark blue. One, two, three, four, five, six. It’s not necessarily as
straightforward as something like bubble sort, insertion
sort, or selection sort. But are there some advantages here? Well, the answer is, yes, there are. In the worst case scenario, we
have to split up n elements. And then we have to recombine them,
effectively doubling the sorted arrays as we build them up. So we take two one-element arrays, and
we turn it into a two-element array. We take two two-element arrays. We make it into a four-element array. And so on and so on and so on as we go. In the best case scenario,
sort of like selection sort, the array is already sorted,
but we don’t know this. We don’t know this until we split it and
recombine it back with this algorithm. There’s no sort of shortcut here
other than doing a search beforehand. But that’s going to
add extra time as well. So the result here is
that we have n elements– and we might have to combine them
if we’re doubling– log n times. Mathematically, that’s how it works. And so actually, unlike
the other algorithms we’ve covered, in the worst case
scenario, the runtime of merge sort is O of n log n, which in general is
going to be less than or faster than n squared. In the best case scenario, because we
still have to go through this process again, it is still n log n. So in the best case scenario,
it can be slower than, say, bubble sort, where the array
happens to be perfectly sorted. As you may recall the omega
there is n, and not n log n. But in the worst case or
maybe even in an average case, merge sort is actually going to be
faster, at the expense of maybe taking up more memory because we
have to recombine and create new segments in memory
for our sub-arrays. So merge sort is a really powerful
tool to have in your toolbox once you understand recursion, because
it can make the speed of sorting an array that much faster. My name is Doug Lloyd. This is CS50.

10 thoughts on “Merge Sort

  1. I want to know if it is necessary to insert into the above Pseudocode "compare which first element is the smallest between two sorted arrays" before "Merge the two halves together"?

  2. is it just me or is this algorithm WAY more complicated than the other sorting algorithms? It seems like, while this algorithm may complete its goal faster than the others, it would take more lines of code to write than the others. Am i wrong about that?

  3. would you mind check some sort of bottom-up-wo-recursion merge sort implementation but just for 2^x numbers here
    https://www.youtube.com/watch?v=tVsWiV95Mxw

Leave a Reply

Your email address will not be published. Required fields are marked *