Merge Sort: Understanding & Implementation | Edaqa Mortoray | Skillshare

Playback Speed


  • 0.5x
  • 1x (Normal)
  • 1.25x
  • 1.5x
  • 2x

Merge Sort: Understanding & Implementation

teacher avatar Edaqa Mortoray, Programmer, Chef, Writer

Watch this class and thousands more

Get unlimited access to every class
Taught by industry leaders & working professionals
Topics include illustration, design, photography, and more

Watch this class and thousands more

Get unlimited access to every class
Taught by industry leaders & working professionals
Topics include illustration, design, photography, and more

Lessons in This Class

7 Lessons (40m)
    • 1. Introduction

      1:09
    • 2. Divide

      4:54
    • 3. Merge

      7:43
    • 4. Complexity: Divide

      6:01
    • 5. Complexity: Merge

      6:39
    • 6. Stable

      2:21
    • 7. Code

      11:29
  • --
  • Beginner level
  • Intermediate level
  • Advanced level
  • All levels
  • Beg/Int level
  • Int/Adv level

Community Generated

The level is determined by a majority opinion of students who have reviewed this class. The teacher's recommendation is shown until at least 5 student responses are collected.

29

Students

--

Projects

About This Class

Master the classic programming sorting algorithm.

Sorting is a key activity in programming, and you should understand how it works. Merge sort is a common approach. By learning this algorithm, you’ll improve your understanding of sorting. It serves as a cornerstone to your algorithmic knowledge, helping you in your job, and improving your interview performance.

In this class, we’ll look at:

  • How the merge sort algorithm works
  • The time and space complexity
  • An implementation coded in Python

Ask questions and I’ll do my best to answer. I’m here to support you.

For further instruction on programming and interview preparation, check out Interview.codes. A site I created to refresh your knowledge and help you succeed at interviews.

The code I use for the final chapter can be found in my GitHub repository.

Meet Your Teacher

Teacher Profile Image

Edaqa Mortoray

Programmer, Chef, Writer

Teacher

Hi, I'm Edaqa, a programmer, writer and chef.

For over 20 years, I've been following a diverse and exciting career path. My journey traces through several countries, filled with great people and culture. I've dedicated my time to numerous startups, and an abundance of side projects.

There's so much I'd like to share with all with you -- from programming to cooking, to the unusual creative endeavours.

I want my classes to give you the confidence you need to succeed, and the curiosity required to make the most of life.

Join me in my continuing adventures.

Recently I wrote a book "What is Programming", a dive into the fascinating profession.

I've also taken up the mantle of food stylist, as I started Edaqa's Kitchen last year. Perhaps soon ... See full profile

Class Ratings

Expectations Met?
  • Exceeded!
    0%
  • Yes
    0%
  • Somewhat
    0%
  • Not really
    0%
Reviews Archive

In October 2018, we updated our review system to improve the way we collect feedback. Below are the reviews written before that update.

Why Join Skillshare?

Take award-winning Skillshare Original Classes

Each class has short lessons, hands-on projects

Your membership supports Skillshare teachers

Learn From Anywhere

Take classes on the go with the Skillshare app. Stream or download to watch on the plane, the subway, or wherever you learn best.

Transcripts

1. Introduction: my Name's Ed equal Monterey. And today I want to talk to you about Merge sort, one of the classic sorting algorithms and one that you should know. I'm going to go through the basics of the hour, how it's constructed. It's one of the classic divide and conquer albums we go through one step of splitting things up and then another step. Bring it back together. This is something that comes up occasionally in programming. It's one of those common albums that could be adapted to various scenarios and during an interview. It's one of your go to algorithms to implement and to show that you understand sorting and how it can be done, and you can build other albums from it. After I've explained the album, I'm gonna talk about the complexity about it both the time and stays complexity and see how we arrive at that and how you calculate it. This is also helpful for an interview when they ask complexity questions anti and getting with your complete example of the code step for step, showing how everything works and looking out for a corner case and giving working example. So let's get started with the explanation of 2. Divide: so the purpose of sort is to order a list of items. This could be a list of numbers like we have. Here are a list of objects, strings or whatever you want. The goal is to get them in some sort of order. In this case, we want to get them in ascending order. Sometimes referred to his natural. Ordering in a programming language is often means that one is less than the next one. And when we get to the code will see that the only operator reaction to use is less than so . How does merch store get these items in order? We can't look at this is a big hole and decide what order they're going to be in merge. Sword is a divide and conquer algorithm. So what it does is it splits up the problem, is smaller ones and solved the smaller problems and then re combines it to get the big list in the end. In other words, we don't know how to sort all of this at once. But if we had just two numbers to numbers, we could compare and say, Look, the four is less than the six and order those. And if we had multiple lists of things in order, we could combine together by taking the one that's the lowest in each side imprint together . Let's look at how murders or it works. First part of divide and conquer is the actual division. Here we have a big problem. Where to split right in half in the middle's. We're gonna make the dividing line right here. When did they want to split there? To get the problem, to be half the size and then I'll draw out with the right half. Looks like draw. The right half here should be the same as it is above. And the over them actually does this. The album is gonna move the numbers down. Two different array. There is an optimal way to do it. We don't actually move them down, but I'll talk about that a bit more. During the complexity analysis, it's now. We had half the problem over there. It is a still too big dissolved right now. We need have fewer numbers to compare, So let's split this in half again. So now we can produce two more halves. We take the left half and copy that down. I see. In a naive I grew them. We could actually do this. Copyrighted the code issue. In the end, I'll ask you copy it down this way. In the original coat, three split this into two again. So those are the two halfs there? We split it down and on the we couldn't order the whole one. If we look down here, it's relatively easy to compare two numbers and put them in order. This one right here, we know while five is less than six, so we don't have to reorder it. Nine is not less than two. So we're gonna have to flip that one around. So I'm gonna break down all of these, first of all, and then we'll show each individual one whether we're gonna swap the order or not run through this a little bit quicker. There we have all the items split down into a list of two that we can easily compare. If if this wasn't an even length, you might have one that are only one long and in some forms, the al with them. You can actually split this out to be further and say, Look, we're going to put this down into individual boxes or you can keep them his boxes of two and then rewarding them this way, so he wanted to extend it further. What your option would be then, is to say, Look, we have a box of six and a box of four, and then we go all the way through. So in this approach, we've literally broken it down into individual items. So each list has only one item in it. You can approach it this way or we can skip this step. The next step is going to be exactly the same. And I'm gonna show the next step just a few of them here. But then we'll move on to the next part of the algorithm will be recombined them because basically what we're doing now, we have these and you can see the goal here is to re combine these grab green issues. We're gonna re combine this and what do we want to recombine into we're gonna compare? Is the right side less than the left side in this case? Yes, it iss. So we're gonna compare them, and when we re combine them, it means we're gonna shuffle them back together. We have a four than the six. And it doesn't really matter whether you break it down to this level or you go directly from here to here. Code wise, these are very similar and they're both options. It really depends on what you're doing and what the approach is, whether you want to do one of the other. As you're seeing the code, we're going to have to deal with one case anyway, so it's not terrible to split up to that level. So then let's move on to show how we re combine all of these, we're gonna start these in the top, and then we're gonna re combine them. 3. Merge: How do we reassemble the individual lists? That is, we have these two numbers and we know they're blocked like this. So these are actually grouped like this. We'll see this in the code. How these air kept close together. They're little blocks. Doesn't make a big difference. You could start with an individualist. It's well, and what we want is, we want to bring these two numbers together. How do we bring those two numbers together? So we want to put them in the order now, visually and for us at a high level, As we think we're not machines. Very obvious. The four comes to a little bit. Six, but what does that really mean? What are we really comparing? We want to check. Well, is this one less than this one? If it is the orders, Okay. See, you can actually check Is six less than four. So is six left than before. The answer is no. And we answers. No, we could say Well, we can swap it him. That's one approach. Now that approach will work. You can say we can swap it, but it leads to one problem that I can get back to later something called a stable sort. And the stable sort means that if you have two items in here, they have to retain the same order song and mark those ones a little symbols right now and put a green on up here. That shows up well and I'll put to orange ones every here do you want to? Now, if we did it with less than we're not gonna have a stable sort. So just gonna have to trust me for a bit here and say This isn't the correct comparison to do. What you want to do is you want to put to compare the second one's There's a second is four less than six. The answer is yes, fours less than six. So four comes first and then comes the six. That's good. Then we could do the same for the next one, and then we get to the five or six case. Now it's going to do the comparison again. We're gonna put the two boxes in, and this is the one where the comparison is going to fail. Us is six less than five, and the answer is no, it's not. So we keep the same order we transfer it. As isn't say Look, it wasn't less tense. We don't need to swap. Then we continue with the last one. Okay, so now we've done one layer off the merging. Now we have a list of the two. What's important about these lists now compared to the original lists of to combinations and that these lists are all in order and that's important for the next face. This face was rather trivial. It's the next phase with the out of them or the code has to do something a little bit more complicated. So we have these two lists here and again, we won't emerge them, and we won't emerge them into one list. And this is gonna be for long, cause those four items in it. So how do we merges into lists and this can be done? And I say pointers, but they're more like indexes. What pointers? A common term. You're gonna have pointers in each lesson. You're gonna point to the 1st 1 h less you're gonna say, Look, I'm pointing here now, and I'm pointing here now and you get under the same comparison that we had before. This defines the right one. And this defines the left. One you're going to say is one less than four. And you say, Well, yes. Well, that means the one must come there. If one is less than four, then we have 21 is the first item in the list. Then we take this pointer and we move it along. That's great. Now we have the same compares Yanks. We have items left on the list. Now we say is three less than four. Well, it ISS So we write the three in here, and then we take this point, Jeremy, Say, look, we're now at the end of the list. When you then the list, you could do a lot of special processing the code, but the same basic logics the moment you're at the end and the one left you're gonna copy from this list, you say, Well, it's going to before and in this six, whatever remains, you're gonna move the pointer long show. The point will go to here until against the ends. And then you fill the ruling. You filled out the list so you could have left that last one. Okay, so now you have an order list. That's four long 13 boards, six double the size of previous one. The list is still ordered, and if you imagine your head that same basic process can work as the list Get larger. You can continue to merge them so I'll quickly run through the other side as well is to less than five. Yes, to is less than 52 comes in. Here, take this one. Move it along to here is nine less than five. Note. Nine is not less than five. So we're gonna take the five instead and move it along that we're here. So next comparison, if is nine less than 69 is not less than six to the sixth goes in next. Then we move this one to the end, and there's no comparison left to do. So we copy remainder this list and we get the nine. And that leaves just 2569 by 13462569 Both these lists are independently, sort of there to sort of lists, and the hour then we used here to join them works for larger lists as well. It was not limited to it works for any size. So now we can actually merge these lists as well. It's gonna be eight longs. We're gonna have all the space for all of them. And there's a little bit quicker now. So, you know, I think so long If we start with the pointer, started the pointers in each one with a pointer here, and it's gonna put a dot on it is to less than one knows. The one goes first that we move it over. Three is to less than three. Yes, three. Right to in. Then the duck goes over to the five. Is the five lesson three that? No. So we write the three in move the dots. It's a five. Less than four. No. So we write the foreign move. The dot is the five less than the six. Yes. So we write the five in and now comes One of the interesting comparisons is six less than six. No. So we write this six in now, come back and explain this later that this is actually this six and this is this six because that's comes next. And then we'd have been nine. As we move through the list. So there we have the complete sort of list of 12345669 This isn't sorted order, and we went through the various steps to do that, merging lists along the way. 4. Complexity: Divide: What is the time in space? Complexity of Emerge? Stewart. If we started this point here, this is the first half the album. This is the part where we're splitting it up. What is the time? It's based complexity of this one. And usually when we talk about this, or always when we talk about this, we have to define what exactly are we counting in sorting algorithms? Typical. You count the number of comparisons you did on the assumption that comparisons are slow. But if we look at this one here in the splitting phase, we have not done any comparisons at all. So it actually has a constant cost of, well, nothing. But we never actually say nothing is constant costs. There are no comparisons done here. However, you may actually want a count the number of copies you do, because in a lot of cases, copying is more expensive than the comparison. And this depends how the objects are stored in memory. If this is a large option where the whole item has to be copied, the copying can be slow or if we have a scattered memory model, coughing males too slow. If these air individual numbers or references to objects that copying maybe fast. So it depends on what we're counting. What the time complexity is here. If it's comparisons, there's no comparisons done here. But if it's copy operations, well, what are the copy operations that we do here? We start with a list, and then we split into two individualists. And if you see on each side, we copy half of the numbers. So in the end, divided by two But then we do it twice. So even though each of them is in divided by two. So each side here is in over two and over to really what you have overall is you've done n copy operations. Now in your throat it down again. Here you do end again and and again. So this is the number of copy operations that you're doing every item being copied. So what does it add up into the end? So the trick in time complexity or complexity is now to figure out, How many times did I do this copy operation? This could be a little bit hard to think about how many steps of their involved when we split something and 1/2 we have to count. How many times does this and generally do in half? You can think, Well, I just know this. I just know that this is going to be something like Log. And I just have to know that because that's the sequence and forms. If you want to convince yourself this if you don't just remember it, the opposite ways to start at the bottom Is that the way to think of this from bottom up? Let's think about how many items earn each list in the layer. So if we call this one layer zero, this is the zeroth layer. Because we love counting from zero. It has one in there. Now, if you put a l one, how many items reach later? Now we have to now the third layer washy l two l two layer sale tunes. And three, we have four items. And at l three, we have eight items. So every step up every step in size, we've doubled the size and we get that. And this is a pattern you should recognize in programming. 1248 16 32 64. And this is the pattern of two to the end. So to the end means every time we go up, we double the amount. And so you just have to know the opposite of that is for the inverse is log in. If we want to figure out how many steps to go down, you take a log in and this is related to to the end. The exponents, You can always think going up. What is the exponents? Increase in size going up. And these are the number of copy operations we do. So this was the basis going up. So they go up because he doubles each time goes up. So we know it's to the Inish level, and we have log and going down. But this only kind of tells us the number of levels we dio. And so if we're looking for the number of copy operations, we know each level. We have to copy every single item. So even though we've only copied half of it here, we have to do that twice. So in every level, we do twice as many copy operations. So we know we only need log and levels because we counted up and we know to Danny's time but on each level, we have to copy end anthem. So we're gonna have and long in those amount of copy operations. Now we have to do, and as we often do, we're gonna go. We're gonna put the big O on it. Everybody likes the big O Swift over and log, and and that is the number of copy operations in the merge source in the first half. A lease is just the first half, but we'll look at the second half after this. So what's often asked instead do is instead of copy operations, is what is this space complexity. And this is very closely related to the number of copy operations. For every time we copy of value, we create a new place to store it. And so this is a space it requires. So every copy actually indicates another bit of space. So we can actually say that the space complexity is the exact same as the number of copy operations in the first half of the algorithm. There is a more optimal way to do this because if you're thinking your head well, I don't actually have to copy this. I can just pass pointers down. You're absolutely correct. There is an optimal form. We could erase this. It does improve the complexity of the first half the algorithm. Second half gets a little bit trickier, so let's look at the second half now. 5. Complexity: Merge: So what is the complexity off this half of the algorithm? We said before comparisons might be the most interesting thing to measure. So how many comparisons are there? And there are actually comparisons in this time to be like the 1st 1 we take the to us? There's one. Comparison is therefore less than six. Another one comparison, one comparison, one comparison so we can take the level approach. And yet how many comparisons it take to get from each level? The next one Speaking of groups, so in l zero and we want a group. How many comparisons to take to form this group? It takes one comparison one there, one there, one there, one there. Now in the second group. How many compares it take to get from these groups into this one? So we're gonna put this at l one say, Well, how many comparisons? A take. Well, this depends on what the items were like. We know there has to be at least two comparisons. There might be 1/3 comparison that goes in there, you know, it could be 123 What is that number in this side to It could also be 2 to 3, and you see sort of a pattern here approach when you go to this trouble here. Level two. How many compares to take to go down to this one? Well, in the highest account, if you compare from 63 to 3 to get each side, if the pointer moves roughly through them, you're going to have seven comparisons. If you're really lucky, you gonna have force. If you exhaust this side first completely, then this side you'll have forced. You have 4 to 7 comparisons, but there's an upper bound to all of these. And that's what the interesting thing is here is it relates very closely to the number of items in total, and you can always say, Look, even if the pointer goes beyond the end, even if this was exhausted first you still have to do comparison a shadow comparison to something. So instead of the 4 to 7, you can take an upper bound and say, Well, this is clearly close to eight, and that's actually the number of items here, and this one here, the group to say, Well, this is bound by four. We know it's gonna be bound by that it's always it's always. It's slightly less than number of items. It's more than half slightly less in here there, too. And so you see, it doubles again to 48 We don't have another one here now. I started a level zero. You think? Well, you know, that's probably not correct. You could change the one you changes toe. Want to start one instead? And what you're doing Time complexity. Are you doing any type of plexi analysis you can feel for your changes number slightly back and forth to help you find a pattern. All right, so you can do this and you could see this pattern 248 But you can actually need the pad in this case is good to identify patterns. One in your interview and you're working on the board. Try to identify these patterns. It really helps. It really helps your thought process, because at this level here, we said we actually have to, but we have four groups, so we actually have four times two and this level to level two. We actually had only two big groups that were combining, So we have two times four and the bottom one. We only have one more cluster to combine the group of to us. We have one times eight. That means that each level we're doing eight comparisons. The maximum compares surgery. There's a few less, depending what happens. So in each level you actually have any comparisons. So they say with and comparisons and comparisons done in each level. Now, how many levels are there this again? You know, if you're doubling in size each time, that was his first number, and I see it's the same number of steps as in the first part, deconstructing If you split something in half and then recombine it, two groups at a time. You have the same number steps. So we know that this pattern, the exponential pattern, the inverse is the log in and for the first scientist, long end. So the number of comparisons we have is in log. That's the number of comparisons, and that's inches one. So that and log and becomes our big o complexity and log in comparisons, we have to compare it log and layers. Every layer has to go through and items potentially slightly less, but it's close enough, so we have an upper bound of end log and comparisons. What if we want this space complexity instead? If you flip this over, this would look exactly the same as the 1st 1 you're splitting into two. And so we knew the space complexity. The 1st 1 waas log end times n, which is interesting. But in this case, the long end times and is a space complexity was exactly the same as the time complexity. If we're measuring compares so space complexities that now, if we're measuring the number of copy operations for time complexity instead of space complexity or instead of the operator, it's always gonna be in long in. This is how much memory it takes. So in the second step, basically, everything is in law again, not sing complexity of this except end. Log in. Now, when you're combining of blacks, issue End log. And this was the highest complexity we had of everything. The space operator comparison space comparison. And if you combine the two stage together, you have n log in plus n log and or lug, and in you end up with just n log and in complexity analysis. So if you had this o. N log in, so just do it and log in again. And Long n Plus n Log in This simply equals big Oh, and log. And that's what makes this problem really interesting in time. The space time complexity. If you're measuring the number of comparisons, what's the time? Complexity. It's in law. Get if you want to measure, What's the space complexions algorithm? Oh, it's n log end. If you want to measure how many copper operations you're doing, which is usually similar to the space complexity, it's also end log. And and this is one of the easier ones. Understand Space tanker Plexi. Just understand the divisions tends to be an exponential in one way and lager in the in the other way. And that's the basics for understanding the space time complexity off the merge sort. 6. Stable: So we have this sort of list here, and I pointed out these two sixes and it made a notice saying of comparing him. And it talked about the comparison operator. Which way we compare why it's important. If you only care about the final ordering, it doesn't make a big difference. Which will you compare? But there's something called a stable sort, and a stable sort means that if you sort of list of multiple times, you always gonna get this seem ordering. And if there's two items of the same type in the first list. So we have two sixes, the end up in the same order in the bottom. So we have this one and the two dot Here's the one green one. What it means is that that six up here because it's hired left most accomplice. It has to be left most in the bottom. And so the orange one, the 21 has to be the right most one, and this is important for a state will sort in a long time. Stable store is important because you wanna have a preacher Sherman List. You want to make sure if you sort this list you always end up with the same ordering because if you swap these items, if you swap these the result in a non stable sort of still technically valid. But if these were objects, you can actually have a different ordering. And generally don't want that generally wanna have one defined ordering, though in many cases it makes no difference. So we wanna have that ordering. So let's mark them throughout their So you have item. But we don't have enough song used the pink ones as well over here for green to mark two. And he was six and six, and these have to keep the order all the way down there on separate sides. This makes a little bit easier, but the idea is that the orange pink one here stays on that side and agreed. One stays on this side, and that has to do with that comparison here when we said, is six less than six. So it's this six. So this is the 2.63 the 2.6 is it less than the 1.6, and the answer was no, which means we don't swap them. If we compare the other way around, we might end up swapping them. So this is the basis off stable sort. And this is why you choose you ordering off the operator very carefully. You can make sure this is stable sort. If you did, you operator the other way, you'll still get a correct result, but it won't be a stable sort. 7. Code: now we're gonna go through the code in Python, and I wrote the python would type annotation, so it's a lot easier to fall along what's happening. But before you look at this segment, before you look at the code I have wrote, I strongly encourage you to write, emerge certain on your own, take your favorite language and actually try to write Emerge, sort. That's a very important part of this class is that you can implement merge sort, and it will be the best way for you. Remember what exactly is happening and how you implement it. And if you have problems, come look at this code or when you're done. Come look at the code for other ideas. But as long as yours works, you should be fine. All right. Now let's take a look at the code former sort in python. So this is my python file and has the very basics of the top. Most of this has to do with the typing and the whole section here. You can kind of skip over this part. This is Ah, This part is about creating a type that's comparable for the algorithm, and I can come back to that. Let's just skip down a little bit first down to the merge sort. And so we can go with the code right away on this. So the merge sort, it takes a list of comparable items and this is about the typing. Here. You can see that I have a list of comparable items and it's going to turn back a comparable item list. This is one advantage, the type meditation python, you conclude. See, it takes a type return something. So this is not an M place sword. We're going to sort and creating new sort of list in return that back. So think back to the way describe this. What cases do we have? We already have the Rikers just set up. You're going to use just this one function to do the Reeker Shin. If there are less than one item, If there's zero items or one items in the list, then this is a trivial case. The list is automatically sorted so we could simply return the items. We don't have to do any sorting at all. Otherwise, we have to split the list in half and we're in a sort. Both sides you know, when I did the diagrams, I just sort of pointed to the middle. When you're calculating this for Koji, actually, at the calle que the middle of that in a python, you could take the lengthy Adams divided by two and python. This is an energy division, ensuring I have a whole energy result. Make sure inviting material get the energy result. And it doesn't matter if you're off on either side, you could be less than half for somewhere than one above half. It makes no difference because you're eventually gonna split this down into a smaller list . Length off one or less. Now, after we've divided it, we do the recursive part. This is where we split it up. In the algorithm. We do emerge sort on the front half of it, and this is items cool in mid and python. This takes everything the front half up to the midpoint and then we merge. Sort the back half. And this is what this doesn't python the items second half. So we merch are the 2/2. So now we have a four in the back half and if you watch to recur shin on this this is going to go through this part of the loop right here until it triggers this return. And so every one of these lists is gonna be one long and that's going to get down to the bottom of the leaf notes, and then it's gonna come back up, bubble up like we saw in the graph and reassign those lists. And so the re combined part is the part that takes it to list in puts it back together. So just like the diagrams and in the white board, the splitting part is actually relatively simple in the re combination part. I didn't worry about memory efficiency very much at all. I'm just gonna created empty listening and add things to it. Now, here's the four at and back at these air what I referred to as the pointers in the diagrams where these are gonna point to which part in the list we're currently looking at in the four and in the back. They point to the current item in the list and the while loop, then says while Fordice's four. So as long as we have anything left in the four list or as long as we have anything left in the backlist, We're going to keep executing this loop and we're gonna get back to the end of him and this makes a difference. When we hit the end of one list, we keep going. We don't stop in, have special code. As soon as we hit the end of one list, we just keep going until we hit the end of both lists. And I have to account for that in my conditions. So there are two conditions inside this list. Either we take the one from the four list or the backlist first, the left or the right 11 of those items has to come first, and so are if conditions do that. If we're at the end of the backlist, Obviously it can't come from backless. So we go to the else and take the one from the four list case that takes care of that. Now, if we're at the end of the four list, then we have to take the one for the backlist, and then we go in this code or and this is where the condition actually comes in. If the back one is less than the 41 and this is the one where he showed on the board. How it compared the right one is less than the left one, and this sets up the stable sort to do this comparison to make sure we aren't sorting things that don't need to be sorted. If it's their back one, we simply take the back one increment, the back pointer. If it's the 41 we take the 41 and increment the four pointer, and we're just adding it to the list each time. So again, these two things the back at conditions take care of what happens if one of the list is already empty, It forces the situation. Which one to take? And then the comparison decides if there's one in both list, which one do we actually take? And then we return out and this out? It's gonna come back upto one. These merge sorts here and is going to Rikers out. And as it gets bigger list is gonna re combine these into longer and longer list until we get to the original out and we do the high level merge sort out there. So that's the basic code and this is include in the show notes. You can get this. I'll give you the repository for this. You can download this and play with this on your own, and I have test runs in the bottom. So I have a test run function here called Test from the Boat. On the test run, it takes a list of numbers so creates in random list of 20 numbers from 0 to 100 at Princeton numbers. We could see it and that it sorts the numbers, and that is a verifying. I'll get back to that verifying a sec, and then it prints this sort of numbers. So let's take a look at a command line What that's going to look like. So I'm gonna run the main program Main Pipe Python Main Pies and Emerged art director in the Repo, and so we could see the unsorted list of numbers. Various numbers from 0 100 the increment in the output. 56 18 14 15. So we see there's two fifteens here. I can't easily verifies a stable sore yet, but this is an excellent exercise for you to actually create and verify that stable sorting is working as well. Can we go through? And if I run it again, this does produce random numbers. We can see what happens there. Not much for output, very basic. So let's take a look at this. Verify as well, because verifies more interesting. I call verify and I passed in the original numbers and the sorted numbers. What verify has to do is it has to check the correctness of the output and the output. Correct, as can be relatively easy checked. So what do we do as it putting a comment check that all the original items Aaron the result and nothing more. This is important because you might have stuck more things in. So we have to make sure that there one the easy ways to do this is I duplicate the result list and every every item in the original list. I remove it from the duplicate. So for every item, that is, unless that means one item is gonna come out of the duplicate. This is an exceedingly slow way to do this, but I don't care, because this is gonna be part of a test suite. This is not likely going to be in production code. If you need to do is in direction code, then that's another algorithm challenge you would have. And that's actually a fair one for an interview as well. My knots got. How can you verify that this isn't sorted order from the original list? You could always start with this because it's a brute force approach, and it works fine. Once I removed all the items, then I ensure that the length of duplicate list is zero and that make sure no new items came in a list. So the 1st 1 ensures that all of the existing items are there. Note that removal. Throw an exception, python. If the items not there so we know can remove existing items, then we sure there's nothing left. This ensures all the items, have a committee accounted for and nothing more. And then the 2nd 1 is to ensure a valid ordering. So now we go through the whole list except the last one, and free every two items in the list. We say we assure that the 2nd 1 the I plus one, is not less than the one before it, and the reason why we do this is because What we said is that we only ever need the less than operator implant this. And if you look back at the algorithm to, we only used less than here is well, and this is very common for sorting albums in libraries in standard libraries isn't a C plus Plus is well, you only use less than, and it makes it more versatile. It makes it easy to implement these comparator, and so we do this, not here to ensure that it's in the correct order. And that verifies the results if you want to see more about that than comparable the top. As I said, these functions air taking comparables the comparable does exactly that, it says only less than has to be defined. So these functions of python, if you run them through my pie, do static type analysis. They will only work for types that implement less than if they don't have less than they won't work. If these functions attempt to call something other than less than like greater than my pie will also throw a static type there because it's not allowed based on this protocol up here . So we have this verify here and I can pump up the number here so I could put 2000 here. Let's create 2000 numbers now and run that in the command line, and you cannot verify the import my hand anymore. So we're going to rely on the verify. And since verify did not actually put out any heirs, we can assume that is correct. And from the small snippet I could see on my screen, these are in sorted order. So that's it. That's the code for Merchant written in Python. And I encourage you if you I didn't actually implant before implemented. Now take the code and take a look at it. There are a few things you can look at them code. Would you like to actually know how many comparisons air done? There's one point of comparison right here. Put a counter here and count how many comparisons were done and look at the code and take emerge sort. And when you're done, call merge sort and then right out How many comm parents were actually done. This is a good exercise for you to figure out whether you're actually meeting the complexity. Things that you think you are should roughly lineup within long. And so if you ran that you would see there's n log and comparisons. Take the comparisons and check that out. Another great exercise for you to do is we also said that this less than this very specific ordering here is to ensure a stable sort Write something that actually verifies that you won't be will use images. You're gonna have to use objects with a comparator on them, and you're gonna have to create new objects and then sort them and then you're verifies going to have to verify that they are actually unstable. Order, not. The two items got swamped. This is another excellent exercise for you to try. All right, so that's it for murder, sir. I'm happy to have sharing you how it works, and I hope it helps you out a bit. And I hope that complexity helps a lot. Feel free to ask questions. Let me know what you would like to see in the future. And don't forget to subscribe to me and watch my other videos as well. Thank you.