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

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:03 As the last bit in in this sorting chapter, let me show you what is actually used in practice. The second method, power sort that you may may have heard of by now as well. Um, this is what what is used as as the sorting method for for lists in Python or specifically CPython. Python is just the specification of the language and CPython is the official reference implementation written in C, hence the name, right? And uh there's others like pi pi which also uses uses the same algorithm. Now uh it used to use Tim sort or still uses Tim sort and one part is replaced namely this specifically the method that decides which merges should come next and that is now done by powers sword uh is by now 5 years ago so maybe not so new but there's more breaking news if you want uh since this year is also used as part of Chrome in the V8 JavaScript engine which is running most of the web client side and also NodeJS server side. So this is a lot more code running these JavaScript implementations than Python I guess and they also switched from Tim Sword to Powers Sword uh more recently.

1:25 Uh if you can if you want to read um Python certainly has the nicer community of uh efforts of writing down the choices why they did things and there's the this is an excerpt from the pull request or the buck report about it.

1:46 Let me briefly say what Tim sort used to look like and also what the top level structure of Tim Sword is. Um, we've we've now seen merge sort as a top- down recursive method or as a bottomup method that puts runs into a queue. There it turns out there's a third that kind of is neither of those two or both combined depending how you see it and that's the the Tim sort version which is left to right there. Um, you find your next run from the current position initially at the left end. Then you take that run and throw it onto a stack of runs, your to-do list that you eventually have to merge. But um you do this one run at a time. You find the next run, throw it on your stack. Then you decide according to some rules in in Timur. It was these interesting rules for the lengths. I'll comment on that in a second. uh that tell you at this point in time you should merge these runs and you'll always do those uh as adjacent runs on the stack that might get merged and once no longer any of these rules tells you there's another merge you should do you continue finding the next run. So in a in a way it is left to right through the array and neither recursive nor bottom up but it has the feature of bottom up that you can detect existing runs. The original rules of Tim's word were of this form that if say the topmost run is longer than the third run, you should merge the second and third. I've wrapped my head around this or tried to wrap my head around this many times and I still find it is not very intuitive to me and there were also various uh things broken in this uh the longer version um I told people in algorithms and data structures for here let me point out that there is also this efficiency problem Tim sword applied on a specific specific list of runs all of lengths one, two, and three in this case repeatedly does these extremely stupid decisions where you're putting a single element into a very long run. So the opposite of the balanced merches that people tried in the game and which are intuitively good and here u this extreme case is so bad that in in the limits Timsur does 50% extra work on top of what you should do and this is very easy to do better here on this specific input. So instead um we can do a different method that's the second from from this paper I mentioned earlier and it has the same structure as Tim sort but now it uses an entirely different rule for when and what to merge namely it has the notion of powers these blue numbers in the picture uh you see them here I'll I'll explain on the next slide where these where those come from and um I'll show you another animation The point here is each boundary between runs, not the runs themselves, gets a number which corresponds to somehow the depth in a in a hypothetical good tree.

5:05 And based on that, we can do this left to right um rule in the following way. Uh the rule just says whenever the new run that we try to put on top of the stack has a smaller power than what is at the top of the stack then we have to merge that stack elements first. So um here we find the next two runs and the boundary between them gets a power of three wherever that comes from for now. This is larger than the top of the stack so I can just add it. the stack always needs to be increasing from top to bottom. Whereas for this two, now this is a violation. Two is not larger than three. So the three has to go. And that means you're supposed to get rid of the three. So merge the two adjacent runs. Okay. And once you've done that, um the stack invariant is repaired. Now everything is nicely increasing from the bottom.

6:07 Uh if you keep going the same thing happens. This one is smaller than two. So the two needs to go. The two is these two runs. So you merge them. Then the two is gone and the stack is in order again. And that's all that happens. So subject to being able to compute these powers, everything is rather easy to describe. Now, if you reach the end of the run, same as in Tim sort by the way, you still just merge top down, the topmost two, then the next two, and so on until you're completely done.

6:46 Where do these power values come from? Uh, the intuitive version is this one. you want to mimic a perfectly balanced binary tree, but we can't really because we want to respect the boundaries of the runs. So, what we'll do instead is imagine connecting the middle points of each of the runs and then let these sink down until they hit one of those green poles. And that is the powers. The number on these the depth in the green tree gives you the powers the depth of the green tree on which the midpoint interval gets stuck. That's where the powers come from. And the reason why why we like this is that okay that's the final merge tree. The computation of these blue numbers is entirely local. You can do this for these two runs. You don't need to know what the rest of the input looks like. And that's crucial for Tim sort because you're doing this left to right sweep.

7:52 You don't want to know you don't want to need to know what comes after what you're currently processing. And if you think about something like peak sort, you can work out that nothing like this works. Where peak sort makes the cut depends on the middle run. And if you're starting on the left end, you don't know yet where that will be.

8:24 Um what's left is the computation of these powers. Uh the code that's used in in uh the simple code is this one. It's based on on the well the definition of powers is just this. It's the smallest L integer L. So that an integer multiple of 2 to the minus L is contained in this blue interval after you normalize.

8:53 What I mean by normalize is imagine the entire array goes from 0 to one the unit interval. Then the midpoint interval here sits on some some range in this unit interval. You get this by taking the midpoint and just dividing by n. Right? And that's what's what's happening here. These compute the two midpoints uh scaled so that they are in the unit interval. And then um if you can while you uh you can take the two midpoints and express them up to a certain number of of binary digits writing them as a binary number. Here this is less than a quarter. So this number would be 0.00 something. This number is between a quarter and a half. So it would be 0.1 0.01 01 something. The power is essentially how many digits do they share? And here they share just the zero. So the power would be one more than that. That's another way to say it. That's the same computation in algebra.

10:07 and uh an animation of the same what you've seen before. So the operation of the stack and the detection of powers is what you see here. First of all, here is the computation of the powers again as this sliding down of of the interval and this this green bounce tree is the light blue here. And you see here um these midpoints are expressed in in binary and they share two zeros and then on the third digit they differ. That's why the power here is three. It's the length of the common prefix plus one.

10:51 Now um the stack here is is shown in the same picture but kind of you have to uh tilt your head a bit. So like like this. This thing here is the bottom of the stack. That's why it's it's drawn as this box. Uh the height of the box is the power which for the leftmost run this left endpoint is zero as kind of a corner case. And then here we have three. So the next box here has height three. Now if you look from below zero three that is fine. There's no violation. The stack is increasing in powers even though it looks like a downward staircase from the left. If you keep going for the next example, the two is larger than three. So here I have a violation. So I need to bump up the three first and merge. That's the newest way how I'm I'm trying to explain all in one picture. Uh you'll be my judge if this is clearer or less clear than the version on the slides.

11:53 certainly more blue. You can also explain the final step, the merging down of the run of the stack by uh imagining a an imaginary zero at the end and then it's sorted. Okay, let me try to give you the argument why this is h + 2 * n merge cost. This lower bound h + 2n at most. And um for that uh let me give you the notation and then I'll show you yet another animation with flying colors.

12:40 Suppose the input consists of runs R1 up to R little R and the length of these runs are L1 up to LR. So these sum up to N the number of elements. Okay. The merge cost of the algorithm overall for that you want to look at a picture like this. the the merge cost is really the length of all these um things created here. So here we have this, here we have these two, then here we have this and this and finally one merge for everything. Um that I can reexpress as remember from the previous form from previous uh for each run how deep is it in the tree. Okay, that's the first thing that is nicer to see in an example. Here are some runs and there's the merge tree that powers sword produces on top of it. And the first step is that we let each run pay for its contribution of all the merges on top of it.

14:11 So this green run here is at depth three. It's it's merged two times. And so it contributes its length three elements two times to the total merge cost. Okay, which also we can uh show by just stacking them on top. So each each uh run now pays as much in total as it is participating in merges. Okay. uh quickly back that's that's this formula uh length of the run times how deep it is in the tree now uh how deep is a run in the tree that I wish again to have this picture somewhere close uh how can I bound the depth of a certain element here in the tree um you can see it also here on example let me use the big one if I have this run ra I and I wonder how deep is it in the tree. It has two boundaries that are adjacent to it. So it has two power values that are adjacent to it. The the key observation will be that powers bound the depth in the tree of that boundary of that internal node. But the depth of say a leaf like this depends on where it is um compared to its two neighbors, the two internal nodes that are left and right to it. And it'll always be below the deeper of the two. That's how binary trees always work.

15:50 And so you can upper bound the merge cost like this. The upper bound here is that depth is depth of internal nodes is less or equal to power and the depth of a leaf is the depth of a internal node adjacent to it. So the larger of the two powers gives me the depth. So what's what's left is to bound the powers of a run itself. And for that I'll I'll show you again in the animation how this comes. Um you can show by how this entropy function you can decompose that that's just algebra. Let me not do it. Um you can show if both of these are less than this term then the result follows h+ 2 just by combining terms. So what what you have here is log of n / li + one and then round it up. The rounding up gets another + one. Then you get this plus two with the two becomes this two and the log n / li become the entropy term.

17:05 Why should the powers of a run be bounded like this? That's almost by definition from these midpoint intervals. The midpoint intervals in length divided by n. If they are longer than a certain length, then their power will be upper bounded by this by this raster. Uh I'll show you in the animation where it's a bit cleaner. But here maybe you can see um for this one.

17:51 And because we know that the midpoint interval of a run, this one, this blue line needs to be at least as long as half of the run that it starts in the middle of. That's what we use here. And so taking it together with this we can upper bound this by just solving for p in this inequality.

18:20 The way um I visualize this here is again we have our midpoint intervals. Now I pretend that they are cut in half and or cut into two pieces and each piece belongs to its run again by the color. And now the last step is what is the power of a run? It's essentially log of this length. So I can test for each in the recursion of power sort. I would test whether it sticks on this topmost green pole. That's this orange tick here. And then the next level has this and this tick. So powers sword would let them sink down like this. But now we do one more step in the analysis. We ignore where these orange lines are and uh basically let them move around. If the blue line is small enough to fall through two orange ticks anywhere, even if they're placed differently, then um I'm going to do it. So I'll let this uh line sink down further so that ultimately what what determines where the line ends is only its length and not its location in the array.

19:35 So that the line here lands in this interval is because its length or 2 over one just length one is between n / 2 4 and n / 2 to the 5. So it sits at this level five. And this means this pile of runs could have been at depth five. So it could contribute its size five times to merges. Here it actually only contributes it three times. That's because the analysis just gives an upper bound, but it could have cost us up to five times this too. And then um the rest is summing up the terms. what's spelled out here is the same as on the slides. Okay.

20:33 So that analysis uh is maybe at the at the boundary of what I would want you to know. Uh there's a bit of handwavy parts left. Um but I think it's rather appealing that in principle the idea of the analysis fits on one slide even if the details may need a bit of may need a bit of extra explanation. So overall powers sword seems to combine the best of these options. It achieves the same guarantees as peak sort but also works in this left to right fashion that Tim sort liked or for which Tim sort is liked um which contributes to locality of memory accesses and so on. and uh seems to have very little overhead in in practice.

← Video 4-6: Merge policies and PeeksortVideo 5-1: Divide and Conquer recurrences →