Video 4-1: Mergesort

0:03 In the next section, we'll look at merge sorts as the first example of a sorting algorithm that works well and the one that provides us with our upper bound for the complexity of sorting. And I somehow wanted to do this question first.

0:33 Let's jump here. I expect that people may remember merge sort from somewhere else. And so in uh in the hope that that's the case, um maybe out of these ridiculously many answers, you can pick out what the worst case complexity is.

1:33 Okay, I think uh the votes are in. So there's a a clear preference here and uh that is also correct. Buff and login. Let's briefly um revisit what merge sort does. Uh first of all, merge sort has one key step which is called merge and it takes as input two sorted small lists and it merges them into one big sorted list. That's what the diagram is supposed to tell you. Uh on an example what this looks like is here's your first sorted input. We call those runs as well. Uh so here small bars means small value and so on. How do we produce the sorted output from these two sorted runs? Well, the smallest output in the result has to be the minimum of the entire input. And because these two are sorted, the minimum is one of those two elements. So by doing one comparison, I know which one that is. And here it's the one in the left. So I can uh write that to the output. And I've made one step of progress in my merge step. Another same problem occurs again. What's the next smallest the next element in the output? It's the next smallest remaining or the smallest in the remaining input.

3:01 So I again compare only the leftmost of my runs because these are the only candidates for minima and the smaller one wins and moves to the output. And I keep going like this until I'm uh I'm done. And done can mean two things. I can either have all elements on the right hand side or as in this case I've used up one of the two input runs and at this point I know I can just copy these over without looking. That's merging and um I trust that you've you would be able to come up with code to implement this procedure that is not a sorting algorithm yet but we can turn it into we can turn merging into a sorting algorithm uh by a recursive procedure.

3:51 Um and here just in code again I've I'm assuming you've seen this before. So if you want to sort a certain range in an array that's the general recursive step initially we will call this with the entire array zero up to n.

4:13 Then I'm uh computing the middle point unless I'm already done. If I'm only a single element or no element then I stop. it's already sorted otherwise I find the middle just by computing um the middle between L and R around it and I call merge sort recursively on the left and right half. After that I do have a sorted two sorted runs which I can feed as input to my merge procedure and that produces the final entire sorted list. Uh, one caveat for merging the way I described it in this example and kind of all uh, usual implementations, it needs a buffer to write the output to. There's two symmetric versions. You can either first copy your inputs somewhere else and then merge back into where you came from or you merge into a buffer and then copy it back as it's on the slide. Um, both essentially comes down to the same thing. You can, there's twists and tweaks to that. You can just copy one run out and merge back into the gap.

5:17 That also works. You can also take the second run, move it out, and merge from right to left. All of these uh variants also work, but they all need a linear amount of extra space here.

5:32 Also note that um I want to be that's the part where um I want to be a bit more precise than in in uh introductory modules. Let's uh compare a bit how fast this is or how much this costs to do sorting like this. And the cost metric we'll look at is something um uh I called element visits here. And this is a bit of a mixture between just counting comparisons and also counting accounting for the memory hierarchy effects. And in merging we need to read and write each element twice. In this in this step I need to uh say here read it once at least and then copy it to the buffer. That's writing reading once writing once and then the copying back does another read and write. So each element is touched twice for read and write. So the overall cost of merge sort can be written as a recurrence where um we have 2 * n element visits at this final step.

6:42 N for the merge and n for the copying back. And so the total cost CN in terms of element visits is is zero if I have nothing to do. And otherwise I have the two recursive calls and the 2n from these n here and here from the final merge. Okay.

7:02 Now this uh this recurrence with the rounding up and rounding down is a bit intricate to solve. So uh one typical simplification to get the order of growth right is to only look at powers of two. Now if you do that here and you plug in n is 2 to the k then you note that this rounding here never happens. It's always a power of two. So the rounding never is needed. So that these two are the same. You have two times the same term namely for one smaller in the exponent and this here turns into two * the k. If you just insert this, if you just unfold this, insert into here, you note that the argument always goes down by a factor two, but then here the argument um outside is multiplied by a factor two, which precisely cancels in the sense that it stays unchanged. The topmost tall term you get from this is this part.

8:05 Then you have the first time you insert recursively this you get a factor 2 * a factor 2 * 2 the k minus 2 that's this term and then from that you also had a recursive term and you keep inserting this all of these terms are just 2 * 2 to the k + one so this is a sum of all identical sumance and you have how many of them well as many as they have to go down in the exponent so just K and uh in total it's 2 * K to the 2 to the K. The two here comes from just this uh each of these all of these are just 2 to the K + one and you have K of them.

9:03 If you reinsert what we know for k namely if n is 2 to the k then k is log base 2 of n then you get um uh for the powers of two 2 n login and that is essentially the right uh the right answer for for powers of two this is precise so the factor two is also in a way real it's there it's not just a bound uh that's of course theta n login um If you want a proper upper bound for the cost for all n, you can always do the trick that the cost is monotonic. So I can go from some number n, I can just pretend that the my input is uh round it up to the next power of two and take the cost for that. Uh then you would suffer a factor two basically and you get an upper bound of this 4n log n + 4n. That's a true upper bound, but it's a bit um imprecise.

10:03 The funny thing with merge sort is you can actually solve this recurrence exactly precisely. There's a closed form and it's here. Uh it needs the fractional component of a real number. So this fractional value of x is x minus the integral part x rounded down. And with that notation, you can write down the the full solution like this. It's rather easy in in a way and surprising that despite this this uh rounding up and down, it has such a a clean closed form.

10:42 And um then you can you look if you stare a bit more at this, you may wonder what this looks like. And it is essentially this leading term 2 n login and then a two uh an n times And then something that looks a bit awkward and it is indeed a periodic function. If you just take this this uh factor in front of n ignore the first the leading order term then this function oscillates between well zero and 0.2.

11:18 So first good result first good answer is it's never really big. And uh second point is it is periodic in log n because of this fractional value business. And so if you plot the difference between zn and this you plot the the linear term um then you get this picture of uh of this periodic function and you can prove that this is indeed upperbounded not just by 0.2. If you read a bit more careful, it's it's a bit more more precise. Okay?

11:58 And again, I don't expect you to know this uh formula here by hand. This is not my point. The the reason for showing this is sometimes these recurrences look like they shouldn't have a clean solution, but that doesn't always mean they don't have one. And even um with that solution like getting these plots of course um you would also be able to do that. Uh but people could uh manage to to work more results out of these um and make make precise statements like this as upper bounds.

12:36 What can we say about merge sort? Um it's it has this n login theta class as an upper bound even in the worst case. That's its main selling point. Yeah. So it provides us the upper bound for the complexity of sorting that I mentioned. It's also stable which is a property that we'll come back to. It's it means that elements that are equal with respect to the sorting criterion retain their relative order that they had in the input. um is also cache friendly in the sense that all the read and write accesses are linear scans over the runs and output. The main downside is that it needs extra space. Even with these little tricks that I mentioned, you essentially need linear extra space.

13:38 let me show you a slight toy um you're welcome to play with if you want. This is again this the solution for the recurrence uh up here. This is the exact cost of merge sort for the just the recurrence and then uh the leading order term and you see maybe you don't see any difference I think is sub pixel difference between the dots here and the uh leading term 2 * n login if you take the true cost and subtract the leading term and divide by n you get precisely this this function that we've seen four. And now we can uh zoom out a bit and see it just keeps repeating like this. Uh if you just look at the powers of two, you only get these these down points. So indeed, you're uh underestimating the actual cost a little bit. And if you um insert this this rounding up to the next power of two, then you're you're overestimating the the actual cost by quite a bit. I of course.