Video 3-3: §3.1 Mergesort analysis

0:00 <Untitled Chapter 1>

0:02 So we left off after discussing merge sort, how it works, and I briefly teased her how fast it is, but I wanted to do the analysis without having it in the last few minutes and rushed. So let's let's have a look at this again in a in a little bit more detail. What we do here is we we count some uh costs that are reflecting the actual time on a on a word ram. Remember our model the word ram we would count every individual instruction as one time step. But that's very tedious to write down our our algorithms at that level of detail and sometimes it's it's not so clear if changing the code slightly would make this better or worse. Um so we'll stay a bit more higher level and instead count something that will definitely show up in the leading order term for the the true cost, but it's a little more abstract more manageable.

0:59 I will count this elementary operations. In this case, we picked the number of element visits. Because that's also something we can um compute for other sorting algorithms and compare the two. So an element visit, you can think of it as just a read or write to an element. Um and we'll do in one merging round we'll do two of these. You have to read the element when you find it in its run at least once, and you have to write it when it is the minimum and goes to the output. Now, you will read some elements many more times, but we count this as a single visit, and the reason has to do with with caches and computer architecture. In a way, think of the visit as having a pointer to the element. Once you have that pointer and you keep that in a local register, you don't really have to pay for bringing it there when you later access it again.

2:04 It's it's something that much more closely mimics actual running time than uh just counting the number of instructions in this case. Because memory accesses on real machines tend to be more expensive than operations inside the CPU. The word ram doesn't make a distinction. It says it's unit time whether you add up two numbers or you load something from memory or you store something, it all costs one. Uh real hardware tends to be different, so memory accesses especially writes are usually more expensive. So that's the second reason why it might make sense to count element visits here. It's closer to what hardware does that is not just the word ram. It kind of lifts lifts a bit in between.

2:51 Uh the third reason is it's a clean measure that's easy to explain. So uh hopefully. So uh we have a cost of two n element visits for one round of merging, where n is the size of the result. If we merge two things and the outcome has length n, then that's the the cost for that is two n. The total cost for merge sort are then written as c of n. So that's the the total number of of element visits when I start with something of length n, so when I start with a zero n.

3:29 And we write this as a recursively defined sequence. If if n is at most a single element, I don't have to do anything, it's already sorted. And otherwise, I have to split it into a left part and a right part and then merge the two. Now the splitting doesn't really cost anything. It's just uh uh it costs one step here. We we ignore this because it's not an element visit. But it's it's very very cheap. But the two uh recursive calls, they have again costs of merge of merge sort. And how much is depending on how big these two parts are. If you work out the exact uh counts here, you see that one one is n half rounded down and the other's n half rounded up. If n is even, then the two are the same. If n is odd, one's one bigger, right? So in general, this is this is the formula. It gives you the number of element visits for merge sort. You can can unfold this recurrence and compute what c of 10 is for example from from just this definition.

4:31 So in a way, we're done, right? This is this is a complete description of the cost of merge sort in our metric of element visits. But in a way, it's uninformative. It's unclear uh first of all, if you if you wanted to compute c of a million, it already seems like a quite a tedious task. A computer could still do it quickly, but it's kind of annoying. And we don't get a good intuition if we have this recurrence and some other algorithm uh with a slightly different recurrence, it's unclear which is better. So what we're after is a is a more concise compact description of this function. C of n expressed directly as as a function of n. Now, unfortunately, there's a problem. If you try to do this exactly, this function is really really complicated. Uh I wish I had the the plot of this, but you can maybe imagine because of this rounding up and down, things happen with a certain regularity.

5:30 If you have uh a power of two, then things nicely uh work out to be even always the same. But if you're in between a power of two, you sometimes get this rounding up rounding down, so you have a a weird uh oscillatory behavior in some terms. Uh and so this this function, what I'm saying is this function is is just very complicated. And it's almost almost the best way to write it exactly is is already like this recurrence, which we uh found not too helpful. So what we do is is approximate it. And that's where asymptotics comes in. It's an approximation for large inputs. So what we're eventually after is um is something like this uh tilde notation. Now here I I could actually express this exactly, but that's a bit only for the powers of two.

6:30 So we'd like to have an expression like this. Um the most precise asymptotic notation asymptotic approximation that we looked at was this tilde notation, which means if I divide this by that by that approximation, the ratio converges to one.

6:50 Now in this case, um what we'll what we simply can do is uh restrict our attention to some input sizes and hope that the ones in between don't behave too dissimilar. Uh the ones that are easier powers of two because then all this rounding never really happens. It's always an even number even if you go down recursively. So if you insert two to the k for n, then this n half rounded down rounded up both becomes two to the k minus one. So these two terms are the same. That's why we get two times the recursive call. And then this is just inserted but two two n, that's just uh the same as before. Okay? Now the the magic happens in the next equality and so maybe it's worthwhile unfolding that a little bit.

7:58 And so I'm I'm inserting the recursive definition uh at this point one more time. We used it once to get from this to this. Okay, so I'm assuming that k is not too small, then we get uh what's after the first equality sign.

8:24 If we insert this one more time for this one, we get two times and then what we had here. So another two times c of two to the k minus two now plus this term where we insert k minus one.

8:45 And don't forget to carry on this one. Okay? Is it clear how I got to this step? I'm inserting the recursive definition. Now uh you can you can keep going like this, that's one thing. And you can try to spot a pattern. And for that it's it's insightful to uh expand this multiplication. So we have two twos in front of this.

9:14 Sorry. Two to the k minus two. uh I split this up, so it's two to the two times two to the k minus one. And we keep this one.

9:32 Now as you may see, these are powers, so we can just add those up. And it turns out in both cases we get the same num we get get the same term. If you further insert the expression, you will always get the same two to the k plus one because you always add a factor of two and make the second second factor uh a factor by by a factor of two smaller. Okay, Uh many factors in that sentence. Um You make K one smaller, but you add a factor of two outside and that the two things just cancel. And this one, you keep inserting until eventually you will hit the first case. And so then you just multiply this by zero and it's all gone.

10:25 So if you summarize what we what we get from this is just these merging terms. And here I spelled them out. But really they're all the same. It's all two to the K plus one and we get K of these. So that's that's the way of of writing the result. Okay?

10:28 Merging Terms

10:50 So in this case, if we resubstitute what K and N are, so if we replace two to the K by N again and K by log N if you solve N equals two to the K for K, right? Then you get get this result, two times N log N. And again here LG means log base two.

11:14 That's definitely theta of N log N, which explains why the worst case was as we had it on the slider question. You have to remember this from last week now. Um What's a little trickier to a little more tricky to argue is that two N log N is also an asymptotic approximation.

11:38 Um This doesn't follow directly from our computation. We've strictly speaking only shown that it works for powers of two. There are separate arguments you can you can basically take C of N subtract two N log N get a recursion for that and bounded, but that's I would I would say that's beyond at least our interest for this module. I think you could do it. Um it's it's not much more complicated than the recurrence we've just solved. But let's let's ignore this for now. Um We'll just pretend we have shown this. And we'll be happy with restricting merge sort to inputs of power that have length power of two. Okay?

12:27 But let's let's keep this number in mind, two times N log N. Don't know if it's a slider question for this, but who has seen something like this for merge sort before, some analysis of that kind? Recursion?

12:55 Master's Theorem

12:55 I mean people probably have seen the master's theorem if you had some undergraduate algorithms class. Which is a way to get to the second bit. Very few people care about the constants in front of it, which is a shame because it allows you to compare this to the next algorithm.

13:26 Um we don't need it. It's it's a way to automate the solution for some recurrences. Um there's there's good references to look it up, but we we don't really use it for any of the upcoming things, so I felt this is not not needed. But I can just send you some references if you're interested. There's good books that explain this well. Um Now putting all together what we learned about merge sort. Uh We've saw we've seen that it has theta N log N running time in the worst case measured in element visits, but that's also true for the the true word RAM cost. This will turn out to be best possible, but we haven't we haven't touched on that yet. Another useful property in in practice that we'll come back to is that it is a stable sorting method. Which means if you have several objects that compare equal, that are A is less or equal B, B is less or equal A you would say that means they are equal.

14:35 Um but it could be bigger objects. Remember the example I brought up last week, I think you're you're sorting a list of employees by gender. There will be many duplicates. There's probably just a a handful of of different values, say. But it would be useful if you could do that and keep people in say sorted alphabetical order what you've done first. So you can sort by last name first, then sort by gender, and then you would have say all the women sorted by last name. If you do this with an arbitrary sorting method, it wouldn't work like this because if things are equal, you they might end up in arbitrary order. But if a sorting method is stable, it guarantees that things that compare equal stay in the same relative order as they had in the input. And in merge sort you can you can imagine how you can achieve this because merging can be made stable.

15:31 The trick is just very simple. If you have the two runs and the smallest elements compare equal you just take the left one first. Take the left one first we add the output to the right. But if you build the output from left to right, which means the one the thing you put in first is to the left. So if you take the left of equal elements first, it will remain in the same relative order. It's it's useful to play this through on an example and just make um have a have a few have a few numbers that are equal, but use different color and then you can keep tracing the order of the colors. Uh Maybe not for now. Okay, the the last bit um it has again to do with the fact that while we all love our word RAM abstraction sometimes we need to look deeper and real computers are not exactly word RAMs. They have other things like memories, memory hierarchies and caches.

16:36 Memory Hierarchies and Caches

16:38 Without going into why that is uh what what the consequences of that really are it happens to be good to have sequential access where you move one step after the other through an array as opposed to wildly jumping at random positions. And the reason is just caches work by bringing contiguous blocks of memory to your cache. So you have one block loaded, but then you use the entire block before you need the next one. That's what cache is like and merge sort happens to satisfy this. It always works sequentially.

17:14 There's a downside in the merging we discussed. It needs a buffer area to produce the output. In the drawing on the slides, you don't see that so much, but really merge sort the merge method that we have gets as an input an array with the two runs in and has some output array where it writes the result to. Again, the little devil on my shoulder says no, you can't tell people something that's that's wrong. It is possible to do merging in place without extra space or very little extra space and still do it in in linear time. But these algorithms are absurdly complicated and fairly slow.

17:56 So while while possible in principle, we have better methods for that. So it's uh all the practical implementations that are really fast use extra space.

18:11 Um There's some yeah, some methods even in practice that build on merge sort that try to not use that much space. They become slower. But it's it's possible, so I felt that it's worth pointing out. It's not something that is usually taught in in undergrad classes.