Okay, so as we, as we said, the sorting problem, again, is central. We showed an O of n squared algorithm and as we said, we can do better than O of n squared. And now, I'm going to discuss or, or illustrate an algorithm, a very elegant algorithm that will sort a list of n elements, in O of n log n, okay? So let's look, think about this, this list here that I would like to sort in ascending order, okay? So I would like to have 1 as the first element, and then 4, and then 5, and so on. Now, how would we, how would we go about sorting this in a more efficient way? Now, one of the, the, the algorithmic techniques that is used for this is known as divide and conquer. Divide and conquer is an approach where I want to solve a problem. I can, the first thing I do is I divide the problem into, for example, two subproblems. Then I try, I solve each one of the subproblems. And then when I look at the solutions of these two subproblems, I come back and I merge these two solutions to get the solution to the original problem. So divide and conquer has three phase, three steps. The first thing is that we divide the problem into subproblems. The second one, we solve each subproblem. The third one, we merge the solutions of the subproblems. Okay? So if we look at this, it's a very natural, it's a very natural instance of a problem that is amenable to divide and conquer because think about the problem as follows. Suppose I give you two stacks of, of, students' papers in a course. One stack is for like half of the, the students in the course. Another stack is for half of the students in the course. And I tell you that they are both sorted alphabetically. So this stack is sorted alphabetically, this sort this stack is sorted alphabetically. And I tell you to put them together. I tell you to put them together. You wouldn't basically take the two stacks, throw them on the ground, and then start looking for the first one, and then the second one, and then the third one. No, you will look at them and look at the first stack here and the first stack here. The first, look at the first paper here. Suppose it's, the student's name starts with A. And the second one here, the first one on the second stack, the student's name starts with a B. You know that you can take this one, this is going to be the first student's paper because it starts with A, this starts with a B. So you take this one and say this one's going to be the first. Once you take this, you look at the second one. If it starts with a A and this starts with a B, this one is going to be the second. But if this one starts with a C, you know that this is going to be the second because it starts with a B. So you take this as the second and you repeat this process. So if I have two stacks of papers that already sorted and I want to put them together, and so that the entire set is going to, is going to be sorted, I can do that in an intelligent way without wasting the, the fact that they were already sorted, right? So, if we have two, two, two sets of, of students' papers that already sorted, I know how to, to merge them together such that the resulting stack is also still sorted. The question is, who sorted these two stacks to begin with? Right? Now, we come into this divide and conquer and we come into a technique, an, an algorithmic technique and a programming technique that is very important in computer science, which is called recursion. Right? So, now I say if I have two, the two halves of the, the stack. Each one of them is sorted. I can merge them efficiently. And then we say, how, who, who sorted these two halves of the stack? Now, let's, let's think about it in a different way. Someone took the entire stack, divided into two halves, and each, each one of them was sorted. How was each half of the stack sorted? Let's repeat the same process. Let's look at this half, divide it into two halves, somehow have the two halves sorted and then merge them. And the same thing with this half. Then how did each quarter of the stack get sorted? We can take each quarter of the stack, divide it into, into two halves and sort them and then merge. Coming back to this list, if I want to live, if I want to sort this, one way to sort it is to say,let's divide this into two halves, sort each one of them individually, and then combine them. So, the first thing I want to do here, is I want to split this into two lists. 7, 25, 13. And here, 100, 1, 19, 4. I want to sort this and I want to sort this and then merge them. How do I sort this and how do I sort this? I repeat the same process. I can now say, divide this into half, into two halves, 7, 20, and this into 5, 13. This, divide this into two halves. How do I sort this, how do I sort this? Of course, it is easy to sort, to a, a list of two elements, but I can even continue with this process. I say, divide this into two halves. So I keep dividing the list into halves and halves and halves until I get here. When you have a list of one element and I say sort a list of one element. If I give the algorithm a list of one element and then I want it to sort, the algorithm does nothing. It just returns because the list is already sorted. This is a list, a sorted list of one item. This is a sorted list, this is a sorted list, sorted list, each one of these lists are sorted. Look at the structure on the, on the board. What type of structure do we see? We see a tree, a tree at the root, we have the entire, the instance of the entire problem. And then we have two children to the root that we have subproblem and subproblem. They are disjoint. Then for this, I have two subproblems, two subproblems. At the leaves, these are the leaves of the tree here. The lea, each one of the leaf has an instance, the simplest instance that we are going to break the problem into. I cannot break this any more. I cannot break a list, this list into two lists any more. I have one item, right? So this is the simplest instances of the problem. When we get to the simplest instance of the problem, we know how to solve it. I don't need to do recursion anymore. I don't need to do divide and conquer anymore. For this one, you want me to sort a list that has one item, it had the 7? I can give it back to you. I say, here's your list. It has the item 7. It is sorted. The same thing here. So, in this phase here, we went from this, from the root all the way to the leaves, this is where we had the divide. We had the divide version. When we are dividing, we are also conquering the problem because when I am dividing, I am getting smaller instances, which, each of which I can now conquer by solving it. So when I get here, I say, sort, it is sorted. Sort, it is sorted. So each one of them is sorted. Right? Then, we start going up, to merge the sorted list. And remember, this instance of having two stacks of students' papers that are each of which is sorted alphabetically, when I am merging, I don't merge them randomly or arbitrarily. I merge them carefully so that I maintain the order. So, let's look at this case here. And I'm going up, right? So when I am going up, now I'm going to use a blue a blue marker. I'm going up. [COUGH] Every time I, I'm going up, I will look at the list. Remember that I want an ascending order so I want the elements to be sorted in ascending order. So I'm going up from here to this way. All right? I'm going this way. I have two lists, each one of a single element. I'm going to say, merge them. This one is smaller than this. So I look at the first element, I look at the first element. I say this is smaller than this, so take this and copy it here. Take the first one, copy it. And then I have nothing left but this 20. I copy it. So when I go up, I'm copying this, this list in a careful way. So I take this, this and I put them here in a specific order. 5, 13, I'm going up, I have 6, 13. 5 is smaller than 13, so I put 5 on the left, 13 on the right. And then the same thing here. I get to this point. So going from here to here is trivial because each list has one item. Now when I go from, bet, from these two to this one, how do I do it? How do I do it? Let me illustrate here. So I have two lists, 7, 20. I have this list, and then I have a list, 5, 13. And now, I want to create this list. That is going to be the four items here. Okay? So let me call this A, and I have this B. And let me call this here, for example, C. Okay? So I'm going to initialize, for example, three indices here. I'm going to say, I will start i here, I will start j here, so I'm, and start k here. So I'm going to start going from left to right on, on all these elements and I'm going to be moving these all simultaneously. K starting here, i starts here, j starts here. And at every point, I'm going to be doing exactly the same thing, which is I'm going to be comparing the item at position i in A with the item at position j in B. I'll take the smallest of these two and copy it here. Re, notice that this is a very small amount of work. In fact, it is a constant amount of work. I am looking at one item in one, in array A, one item in array B, comparing the two, taking the smallest and copying it to C. When I copy it to C, I have to, to, to advance these indices. If I copied the item from A, because I didn't touch B, I don't move, I don't change j, I have to move i one step to the right. If I copy the item from B, since I didn't touch A, I don't touch i, but I advance j. In both cases, because I'm always copying things from A, B to C, every time I copy something into C, I have to advance k. So, let's look at this. We start i here, j here and k here, so they are all sorting at the first position. I compare 7 to 5. Which one is smaller? It is 5. So I copy 5 here. I move k now to this position because I copied. Since I copied 5, I advance j. Now j is, is pointing here. I repeat the process. I say compare A i to B j. Now j has moved, so 7 and 13. Which one is smaller? It is the 7. So I copy the 7 here and I move k. Now it is pointing here. Since I copied 7, now the i shifts one position to the right and it is pointing here. Now I look at i and j. 20 and 13, which one is smaller? It is 13. So I copy 13. We are done with this. We copy k here. Now we are done with this. There's nothing else to compare. I go back to A, copy everything that's left in A here. There is one item, I copy it. So it's a very simple process. I have A sorted, B sorted, I want to merge them so that I get C. If this is A and this is B, I got, I, I can, I can merge them in a very simple way by using three, and this is carefully, okay? I, j, k. When you copy from A, you advance i. When you copy from j, you, from b, you advance j. In both cases, because you're copying something into C, you advance k. At the end, you have the this, which gives us this. I repeat this process for these two, I will get this. Then at the end, I repeat this process for this and this, I will get this list. Okay? So this is how merge sort works. It takes this is an algorithm that's called merge sort that has taken the original list and going through this phase of dividing it into subproblems, smaller and smaller. So I take the list into two halves, each half into two halves, then each one of these into two halves. Once I get to the leaves, which are the smallest instances I want to divide into, I know that these ones are easy to deal with. I deal with and I start backing up to get to the root doing the merge phase so that I get this this list sorted at the end. So, this is how this algorithm work and this is, again, called merge sort. Okay? So merge sort works in this fashion by dividing the problem, the list into smallest lists, sorting each sub-list and then merging the, the smaller one.
