Original subtitles

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