All language subtitles for 6 - Merge Sort English

High in this video we're going to talk about the merge sort algorithm and merge sort is one of the most

popular sorting algorithms that's out there today and there's a number of reasons why.

And there's also some important properties to understand.

One of the biggest reasons why it's so popular is because it's very fast for a sorting algorithm.

If you remember back to insertion sort or this selection sort or any of those that we've discussed in

the past merge or is a order of n log.

And in terms of time complexity which means that it's much faster than some of the other insertion sort

type of algorithms that run at a worst case time complexity at 0 and square.

So that's one thing to remember it's very fast.

And the other thing is it's very easy to understand when we walk through exactly how it works even if

you don't have a strong algorithm or mathematical background I think you'll be able to really capture

exactly how a mergesort works.

So that's something that's very important in my mind when it comes to algorithms because if it's easy

to understand it's going to be a lot easier for you to implement in terms of building the code for it.

The next thing to know is that it's recursive.

So if you've never dealt with recursion or you've never built recursive functions they're actually pretty

similar.

They're pretty easy to understand.

And so I'll draw out exactly how it works so in a program you could do something like call a function

and the function would be something like merge sort.

And then say we're doing Python.

Actually this would say def but you get the point.

There's a function merge sort.

And inside here we're going to be this is where we would call all of the things that we would want that

function to do.

So it could do things like print.

We could add items to an array of different things like that.

We can do if statements all the normal kind of programming things.

The other thing though well what we do with the recursive programs is we actually call

the function itself inside the function.

So we're actually calling merge sort on itself.

And so what that allows us to do is each one of these items will be called again and again and again

when you're calling merge sort because you're calling all of the same properties and methods repeatedly.

And you obviously have to build things in so that the program does have an end at some point.

But what it allows us to do is to break a program down split it apart which addresses number five issue

which we'll talk about in a second and be able to repeat it over and over again as you start to get

into more advanced programming.

Recursion is something that happens a lot.

And being able to understand some of the performance metrics associated with recursive applications

is going to be very important.

The higher you go up in computer science or in mathematics so essentially just understand it it's really

just a program calling itself and will allow you to perform the same task over and over again.

So that's just a very basic idea of what we're cursive functions do.

And they get to me to check marks.

OK so we've gone over the first three and the other thing.

What it is it's a stable sort.

And so what a stable sort is we'll look at just a smaller array right here.

So we'll have three five four three prime and two and just three prime.

So we knew that this is different than the first three.

And so they were to call assort on this in a stable sort.

This would look like this three three primary tube in the front then four and five and that would be

what a stable source looks like.

Which means that this theory is still in front of this theory the same way it is over here.

Now in a unstable sort what you could end up with is something that looks like this

to three prime three four and five sometimes depending on what kind of data you have that doesn't matter.

Other times it can.

So it's very important to know if you're using a stable sort algorithm or if you're using an algorithm

where that means those properties may change.

And so we've got one two three and four and now we're into the last one which is just divide and conquer

and I'm going to go straight into how merge sort works so that we can understand this one.

And so to start off what I'm going to do is just give us a small array of numbers going from 1 to 8.

And so I'm going to go with just three

seven 10

2 3

4 and 1 get almost around the room.

So we have our eight and what divide and conquer does or what merge sort does it uses divide and conquer.

And it literally is as simple as that.

When you abstract it out and this is what it's doing it's going to divide all the elements in the array

and then it's going to perform tasks on them.

So what that would look like is something like this.

Three actually turns almost into its own little mini array then 7 does the same 10 A to our other three

four and one and them so you can see right here we have eight elements and now we're going to start

to do it because they're all spread out now and obviously there would be a process.

And if you're building this with code you would need to create a program that does split amount exactly

like this.

And then what you're going to do is you're going to take and you're going to compare each pair of elements.

So you're going to take each one of these.

And so you'll say is three less than or equal to seven.

It's less than.

So we're going to put this these in their own box and so do 3:7 and then we do the same thing here except

here that actually swap places.

So that's all we're doing is we're comparing each item and then we're putting it in its own broken down

box and then we do the same thing here.

OK now so we've started to put things together and what we'll do now is compare the elements in these

boxes and we'll put it in another one.

So right here we will go and compare three to eight and compare three to 10.

And so we know three is the smaller one out of those.

Then we'd go seven to eight seven to 10 seven the smallest and then eight and then 10.

So that was an easy one because that's already in order.

So we have 3 7 8 and 10 and now we're going to do the same here too.

We're you know it's that it's less than three.

So we look to less than one.

No one's less than that.

So we'd have one is it less than four yes it is.

So we put a 2 there.

Then we look at the three is the three.

Less than four.

Yes it is.

So we put the three there and then have four.

Now if you notice what we've actually done through this process both of these boxes are sorted already.

So we have 3 7 8 and 10 1 2 3 and 4.

And so now all we have to do is do the same thing here.

So we'd say OK is 3 less than 1.

No it's not.

So we know that one's the first element here then is three less than 2 no is 3 less than three.

No it's equal then.

So we're going to put that three there because this is a stable sort.

And then we would go and look at seven and seven would say is seven greater are no less than three.

We'd put that three in seven to four.

Four is.

And then we know that seven is there.

And because there are no more elements in the array we know that the remaining items are the last ones

and there we go.

We have a new array that is fully sorted and we went about it.

Intermediately.

So we went broke it down into each item and then simply sorted those smaller items and start just kept

on putting them together over and over again until we ended up with a completely sorted array.

And that's what.

Divide and conquer is.

And that's exactly how mergesort works.

So please let me know if you have any questions at all about that and I will see you in the next video.