CS 566 – Efficient Algorithms (Winter 2026-27) · unit page · YouTube
2026-11-09, 32:56

Click any sentence to play from there.

The transcript was generated automatically by YouTube's speech recognition and is offered as is. It may contain errors, in particular in concerning technical terms, names and formulas.

0:04 one idea of how to do better compared to these alignment issues that top down merge sort. Cutting runs in in half or cutting runs into two parts is to not even do a recursive approach but rather work bottom up. Uh you may have seen the bottom up version of merge sort in algorithms data structures. Uh it's a side remark in Cedric and Wayne's book. uh you can spell it out as um little algorithm like this. The idea is that um for merge sort you don't really need this recursive structure strictly speaking you can uh just grow runs. The traditional method says I'm initially treating every element as a single little run of its own. That's this part. Um and we have a queue of runs that we still need to merge. So initially every element is its own thing.

1:00 That's the Q. Now uh while we have at least two elements, we get the two front elements out of the queue. Take these out and merge them. So we make just drawing it like that for now. and um that we add to a a buffer Q Q prime that will eventually swap places with Q with. So we keep doing this. We take the two front elements and move them into the other Q. One more round. And then we'll just swap places between Q and Q prime. So we call Q Q prime and vice versa. And now we do the same thing again. take the top the first two things and merge them. It gives a box of four elements and put that to the output. And now I'm um no longer I don't don't have two elements anymore. So I'll uh just leave that lonely run on its own and put it also in the other queue. And again I swap the ros of the cues. And with one more merge I have now one run that contains everything in a in a quick way. That's how bottomup merge sort can work. Now this is not adaptive. It did not even try to find uh sorted segments. But this is very easy to do in this kind of code because instead of starting with individual elements, we can just check um by uh starting at I and then walking with J to the right. As long as things are in order, specifically as long as we're not at the end and as long as the next element is larger than the previous, we increment J. So once we're done this I to J J J J J J J J J J J J J J J J J J J J J J J J J J J J J J J J J J J J J J J J J excluded is a run and we can start with those instead of the singleton elements.

3:06 Okay, in this case uh we can completely avoid these um alignment issues that we had here up there and that we would never make a cut here in the middle of the run because we always pick up entire runs.

3:26 Okay, that's where we want to go. Uh to see if if this is clearer, let's simulate this uh another time. Uh you should read this picture top down. So we start with this as input and then we successfully merge them up by uh not having the boundary. I hope the picture is clear enough. What would bottomup merur do?

4:42 I'll wait a sec to switch over so you still have the pictures. Um, anyone still thinking in the room Okay, eight votes. Uh, it's a relatively clear picture so far. Most people seem to um prefer policy one here. That's the right thing. Um, if you look at it in these pictures, you also see a slight disadvantage that bottom up merge sort has over top down. Um, it depends a bit on on the definition, but uh this could be say top down merge sort. I think this one as well if you round differently. Uh here the merge is a bit less balanced. This last step has a a run of length four and a and a lonely element. And this of course can always happen but this is uh in the grand scheme of things a very minor detail. Um otherwise uh bottomup merge sort works fine for this. It's the same n login leading term. Yep.

6:38 So there's several good ideas in in your suggestion. U let me just repeat the uh the question for for the online people as well. Uh the question was what if um can we can we improve bottom-up merge sort or I guess rather on the right here. Can we improve bottom-up merge sort by using a more clever queue, a priority queue of some of some sorts? And um hold that thought for for a minute. We'll come back to that. Um there's a a slight uh well first the question is what should the priority be? Um it could be the length of the runs or it could be the values in there. I think you meant the values, right? That makes sense. Um so if you merge the smallest and largest values, you have a good chance that you don't need to do much comparison wise. Um the effort for writing out the merge solution still exists unless they happen to already be in place which uh that's a bit less clear there. Uh the second problem with this is that it kills stability.

7:38 This is uh from a practical perspective um this is the main main disadvantage. If you um if you do what you suggest to do a priority queue, it might merge something very far on the left, some far into the right, and if you merge across a distance, the runs in the middle that you skip, you have no control over how equal elements behave. That's why people prefer to stick to stick to um neighboring runs, but it's a good point. Um there's no uh it's not clear that bottomup merge sort needs to stay as it is because maybe let me uh have this still open.

8:34 If you're curious about how much of a difference this really makes, remember this plot, this was the linear term of merge sort. So what what is left? Uh well at the top it's the cost of merge sort just plotted out uh from the recursion and this is standard top- down merge sort. The the plot below here was what if I take the leading the the actual cost and subtract the leading order term and then divide by n. So it's the kind of next next uh term in the approximation by uh asmtoics.

9:10 And if you do the same for bottomup merge sort then you see this this uh this this um jumping line here this periodic function is the same. That's one that's the one down here. But for bottomup merge sword you see there's a much more jumpier behavior in this linear term. And precisely when you're slightly above a power of two, it behaves worse than top- down merge sort, which makes sense because a power of two plus an extra element means this extra element is left alone until the very end and then merged into all the other elements. This is a rather costly operation. And so you see um that in in this sense you can quantify how much bottomup merge sort is worse. Uh on the other hand, if you compare the top two pictures, there's really hardly any difference.

10:04 Question. We could add dummy values. Um if you do that, then that's usually more costly than not doing it. So you could add a dummy value to kind of not have this this very stupid last merge, but uh you pay for merging that dummy value. So I think you don't win. No, but is an interesting thought. Um sometimes this helps. It certainly might makes the analysis easier, but um you kind of make the algorithm slower. Uh so all of this is fine. bottom-up merge sort is a tiny bit worse than top- down merge sort if you apply it to um random inputs. And for uh these these natural merge sorts where you try to pick up existing runs, it seems to be better because you can pick up the runs in the way they occur.

11:14 In particular here for this input, this is what we've seen before, right? So top down decided to cut here and make this nice run into two. Very bad choice. Bottom up merge suit here works perfect. It picks up these runs as they are and it just pairs them up. So if you compare the cost, you have this 128 for bottom up which is very close to this lower bound of age and a good deal better than the top down version. So case solved. But uh unfortunately this is not the typical example. Uh bottomup merge sort has another problem. If there's one run that is substantially longer than the others, the idea of um grouping them in pairs ignoring how big the run is is very stupid. This means this very long run is merged many many times and each time we pay the full cost of moving all these elements and you can imagine this is uh I could make the picture even more extreme. You could have almost all the elements in one long run and just a a very small number of very short runs.

12:26 And bottom up merge sort would still merge this long thing log many times than you have runs there. Whereas top down merge sort here does something much smarter. It uh it cuts things in half here. So it pays a bit more on the right but then it doesn't merge this left half more than once at the end.

12:47 So can't we somehow get the best of both worlds? Um are we really stuck here? And that's the point where is such a nice selling point for algorithm design because at this point you should take a step back and say what are the actual didorata? What do we want to do and then try to have an actual solution for it right and conceptually there's two simple uh two separate tasks. An easy one which is finding the runs in the input that we can do with just a scan left to right like bottom up merge sort did it. And then the second is the question of how should you pair them up and uh as a a model of which of the orders of mergers work better or worse will postulate that we count merge costs which is the element visits from previously in the chapter. So the total size of the output is is proportional to that cost of element visits. And um if you have such a such a merge tree where you're always merging adjacent elements again for stability we don't want to take one on the left and one far on the right um only um neighboring runs are allowed to be merged. Then you always get such a binary tree and the total length of all these intermediate things is what determines the cost overall.

14:16 Okay, if that looks a bit familiar, then maybe you've seen some some of you have seen this before. Uh this is the same as um counting for each leaf how many elements are in there and how deep are they in the tree.

14:44 before we continue with that. Uh let's have a little bit of uh fun with this and you can see you can play a little game to see if you can do better merches.

14:59 So, let me open that. So, there's a link tiny.cc/merchsortgame where you can copy it out of Slatero. where um you can play a bit merge tree designer yourself. So you see here is an input with different runs different runs of different lengths and you can decide to merge them in some order. Uh even has sounds. Maybe I should tell it, take these off. And at the end, you get a rating for how well you've done. And um it tells you whether you're optimal or not. For this simple one, of course, uh the best is to balance the tree. Then you get um get this result.

16:04 Uh let's have a a few minutes of playing with this. Um, I think it helps to get a feeling for what comes next and we can have a little competition as well. So, if you sign up with your name in down here, you can put a pseudonym name in and then we can see you on the leaderboard.

16:43 Okay, there's tons of things coming in. uh you get this little star if it was optimal. The strong arm means you picked the same tree that power sword would have picked. We'll talk about that in a bit. Um I thought let's have first some fun.

17:28 Okay, you've managed to turn off the sound. That's good. Or it doesn't work. Well, as as with some other things, this predominantly wipe coded and Claude decided to write a little synthesizer in JavaScript to reduce the sound to not exclude some external uh resources.

17:49 That's one way to do it, I guess. Okay. So, those who are racing ahead, um maybe you can uh if you want speak up a bit and try to explain how you approach this. Uh I would be curious. Someone wants to uh explain their approach a bit.

18:28 What one approach is just swiping things around until something happens. Anything more structured than that? >> Yep. I mean, the game doesn't let you anyways, right? But yeah, it's a good strategy that that gets you um through many of the first levels optimally that you pick the locally the smallest two or I guess if there's if the smallest two are not neighboring, you need to somehow refine a bit what you do. But um picking the smallest and doing something with it. Yep.

19:35 ah balanced merges where you have runs of similar length. Um that's also a good uristic. Um as with most of these rules in in the specific example, it's often clear what you want to do, but there's quarter cases where it's not so clear, I guess, right?

19:55 Okay. someone played um even another one. Does someone have a strategy to find the provably best tree? What would you do if if like okay extreme case your life depended on finding the exactly optimal tree?

20:18 How would you um try to approach that bit of a hypothetical? >> Yeah. I think that's some similar uristic, right? You you try to uh balance the merges. Balance for me means the two inputs are similar. Uh so how would you argue that this is best possible if your life depended on having the best possible tree, right? Also like the game somehow tells you what is optimal. It it evaluates your solution against an optimal solution. So it must somehow know, right? Unless I'm lying to you.

21:09 So here's an easy one. There's only finitely many different trees, right? At each step, you have a certain number of options of what to do as the first step. You could just try everything. Now, this is called efficient algorithms. So, this is uh not very satisfactory because uh the number of trees or number of options you have grows very very quickly. For the small examples, it's doable though.

21:45 Now we might revisit this game a bit later in the module. Uh for the moment um I would leave it there. Let me just point out that yeah one more comment.

22:12 Right. Y I would even paraphrase what you said and say the the the big runs, they're kind of dangerous. If you make a mistake there, it's always costly. So rather not touch them unless you have to. Yeah.

22:48 So I think this is this is a good idea in the sense that there will be a last merge that you do where you have something on the left and something on the right and then you do a last merge to combine them. What could be the last merge that you do? This is kind of the the opposite direction. Okay, very good thoughts. Um the one thing I wanted to point out is that Max was the person running ahead very early and now people caught up and overtook them. So um sometimes the fast quick uristics are very very efficient to execute but then on the more tricky levels uh you need to come up with a different idea again and sometimes uh if you're if you start out a bit slower um it can pay off here. Okay. Uh, at some point we'll have to kill the fun. So, let me switch back.

23:41 Um, we'll not talk about powers sword right away, but first we'll do something closer to your thoughts uh of the containers left and right.

23:54 uh we'll revisit this problem also later because it is already known under a different name and there in that context we'll see how to optimally solve this but not for now and um as people may know this is uh a question that that I asked myself when I was postto in in Canada um what should you do in this case and is there a principled way to get um a good solution without taking too much time and without guessing too much um of what what will be the quality of the solution. And the result in the end is is two algorithms that are similar in some sense. I'll show you in a second. And they both achieve roughly the same cost, namely this lower bound of h with uh an additive error of 2n. So you may need 2 n extra element uh visits overall. Um but you can argue that also this is not uh you can't improve. If you want to have a bound of this shape in all cases uh the worst case is basically a very long run in the middle and something small and left and right then you have to merge this middle one once and twice to get the two small runs merged into.

25:09 So in this model this uh you can't really do much about this. Uh the first of these methods um is a bit less well known is peak sort which tries to do what you suggested. Let's um think about the last merge and we want the last merge to be as balanced as possible. So if I have a couple of runs here that I don't know yet. I don't want to spend the extra time to read all the runs in initially. Uh, but either way, I can jump into the middle of my array and from there scan left and right to detect this middle run. So, uh, I find automatically the run that contains this midpoint even though I don't know where the runs start and end for the others. Uh, that's the the part where it tries to be a bit more clever. And then we'll um decide the boundary of this run that is closer to the middle point. That's going to be the cut where we cut into left and right containers. Everything on the left and everything on the right. That's will be our last merge that we do. And uh to get there we have to recurse on the left and on the right. And that's it.

26:24 So we cut here and on the left we have a problem of the same kind. So again we ask where is the middle? The this run we now detect by scanning outwards. we find the closer boundary and there again we do the the next merge and if you unfold this you get even at the end some tree of this form. Now the um there's a one one thing where you can be more or less clever and the point here was whenever we start the recursive call we jump to the middle and detect outwards this run in the middle point. If we d if we were just to do this recursively, we might rescan the same run many many times and that's a bit wasteful. It might not overall affect the big O term of the cost, but it affects the constant. And we can do better by just remembering things. Question.

27:34 Uh the point is you don't need to memorize the runs. Um in a way you do this still recursively. So you go first left down. So this is a kind of a a depth first search over this tree. You don't need to have the tree ever fully in memory. Uh I'll show you the code on the next slide that maybe is is clearer. Uh what I want to convince you of is that you don't have to scan this run in the with containing the midpoint several times. Even though it is here this this this the same run it's part of the recursive call you might have scanned it here again. You can avoid doing that by remembering for each of the recursive calls what is the length of a of a run on the left and on the right endpoint and you just pass that in the recursive call. you already have two parameters left and right the range you're sorting.

28:25 So you add two more to say ah and on the left there's so many elements in a run and on the right there's so many elements in the run and with that you can avoid this extra effort of ever scanning a run twice. So over the whole recursion you again find each run just once and uh the rest of the cost is just the merges. Uh you can write this in very concise and hardly understandable code. Uh it's written down here. Um let me instead show you the animation for that. Um is not so important that you that you follow the details of the code on the right. Uh what is what is more important for me is that you get a feeling for we don't have to redetect these middle runs. Um so we start let go one step back. We start the outermost call. It's rather small, right?

29:33 We start the outermost call by finding the run on the left and the run on the right. And then we have a recursive a first recursive call where this is the input. We already know the outermost runs.

29:47 Then in the recursive call itself, we jump to the middle and now detect this this run in the middle. That's this blue one. We find the boundary that is closer to the middle point. That's this one.

30:01 And um this business here with I J G and delta G makes sure that there's a uniform way to pick the parameters so that it works in all cases. Uh there's different different cases depending on whether this middle run um is closer to the right or closer to the left and also whether the runs at the beginning and at the end contain the middle point already. The original publication distinguished poor cases there. Um, I'm pretty proud of the code that avoids this, but it is a bit harder to read. So, uh, there's there's a trade-off. Well, here, um, uh, we found that this is the point where we cut and we pass to the left recursive call that there's no run on the right because we cut at the left end point, but for the left, we still have this detected run from earlier. And then you can step through the through the rest um you can go through this uh on the website if you want to see if you want to dig through the code in more detail then you can do it there. I'm not going to force you to understand the code. Uh just thought it's it's rather um satisfying to me at least that you can put it in this concise form covering all the edge cases without distinguishing them explicitly.

31:28 Okay, almost done. So it cuts another time on this tiny sub problem. Uh so this is peak sort. Um the analysis is a bit intricate. So we're not going to do the full analysis. Again I can point you to some graphical proof on the website. Let's here just prove it by example which is uh let me show you an example. Well, it's not a proof at all, of course. Um, here is the merge tree that results from peak sort on this input that we had earlier where bottomup merge sort didn't do well and top down merge sort did okay but did a lot of effort on this right half. H you see here the comparison of the of the merge cost where peak sort is close to this entropy bound age again and the other two not really. So at the end of the day, we can have the best of both worlds of both top down and bottom up merge sort. And the answer is a top- down recursive method. It just needs to be a bit more careful. Peek into the middle to see where to cut instead of bluntly cutting straight in the middle.

← Video 4-5: Mergesort with sorted checkVideo 4-7: Powersort →