# 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.

So lucky to be following your channel

Is there any point by reuploading these again and again??

the best explanation ever of mergesort algorithm

This is great.

Tpurple of the blocks combines with the shirt

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"?

I feel like I significantly gained an understanding of recursion from this video! THANKS!

Sound not working

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?

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