0:00

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.

Â 0:49

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.

Â 1:55

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?

Â 3:43

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.

Â 4:15

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?

Â 4:48

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.

Â 5:06

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.

Â 5:31

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.

Â 7:03

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.

Â 7:24

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.

Â 8:52

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.

Â 9:24

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.

Â 11:18

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.

Â 11:51

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?

Â 12:23

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.

Â