Video 3-6: §3.6 Python's list sort & Powersort

0:00 Python sorting background

0:01 in the next section I want to briefly show you what is used in Python these days uh we'll we'll cover the part where I had an influence influence on and I'll I'll show you some bits of the of the full algorithm but there will be a few more things we don't cover there's some lovely videos um online that cover the rest if you're

0:24 interested so first of all just to get the name straight when people say python they often mean the program that you run or they mean the reference implementation but these are technically different things so python is just a specification it's one long document or a website that tells you something about an anonomous programming language and how that is supposed to work but it's not something you can run it's not a program instead uh the the correct term would be cpython which is the reference implementation implementation of the Python programming language and it's called cpython because it's written in see um but that's that's all um if you install python that's usually the implementation you get but there are others available uh it's not the only one in existence and so python again defines two ways to sort things you probably know this you can either have a list and say do sort then it modifies the list um in place it modifies the list to be sorted or you can call this sorted buildin function and pass a list and then you get a a copy back that is in sorted order now despite there's being python code where you say sort the actual sorting algorithm is written in C and it's uh it's bloody low-level code um

1:48 that I was I'm happy I didn't have to touch so this was uh the the low-l code was done by Tim Peters we invented timsort um that's the algorithm that python uses for well over 20 years now which is um similar to the type of merge sord variance we've seen it tries to exploit um runs in the input that are already in

2:18 order and well I gave this away already um well it was included in 2021 the official release was last year um so instead of Tim sword it uses it uses the merge policy I'm I'm showing you soon

2:33 How Timsort functions

2:35 here's a rough overview of what timsort looked like and I just want to give you that to the extent that you can understand why people want to do this instead of the merge sord variants we've seen so far uh the way roughly it works is as as follows you don't need more of these details that's again kind of a Side Story I think the whole the whole section is outside of the exam um except for the the high level ideas uh so Tims sword goes one time through the entire array there's no recursion in that sense and it maintains a to-do list of things still to be merged it's a little bit like this bottom up merge sword it's closer to that and so in this case we maintain this as a stack it's not a que like in bottom up merge sword the or or organization is a bit different so you make your way through your list you sit at some point and you find the next run um by code similar to what I had on the slides earlier and you store that on your stack that's on your to-do list you eventually have to merge that run into the rest of the runs now when and exactly how you do this is governed by a

3:49 set of rules um I don't really want to explain in detail because I think they're they're just not a great solution and have never been but uh that's the first thing that kind of worked Tim Peter words um so there's some rules that tell you okay now among the topmost runs you merge a few or you stop and it can go on for a while and eventually it stops then you find the next run put that on the stack and keep going eventually you reach the end of the of the input and then you might be left with some things on the to-do list so you just go top down we'll see an example with this with the new merge policy in a in a second I want to point out why this is um a reasonable way to go about sorting uh one thing that's good I mean it can pick up existing runs but the the second bit our pakur would have done too the second bit is it keeps the locality of reference that's again something uh to do with the hardware and and caches uh but if you read this run you already spend the time to get that data to memory so it would be useful to do something with that uh data while you

5:00 have it and that code because it uses a stack it's likely to do merges with the data it just loaded to memory uh straight away as opposed to like Peak sword look in the middle oh now I know where to cut and let me now forget that I touch this run and do something else that's not as efficient that's why people um like Tim sorder that's one reason why it's why it's fast in practice uh there are many other little tricks I link to a few YouTube videos where someone explains those in a in a high level language as for fun for you if you enjoy it otherwise you can forget about it I just want to mention that I'm not doing the name Tim sword Justice if I would claim that that's all there's there's other things going on uh but they haven't

5:50 Limitations of Timsort

5:55 changed the story started with um a few researchers noticing that there's a a weird thing happening in Tim sorts merge rules so these these weird rules here uh the way to read them is that these are the lengths of runs and so this rule would say if the topmost run is longer than the Third Run you should merge the second and the third and uh yeah it's not intuitive if you do this um it occasionally happens if you have specific inputs that something stupid is done uh again and again you have very long runs where you just add a single element into it so the red is the result but you have this run that is just one element shorter and then you spend all the all the memory cost of loading this merging it and writing it back to just get the Run long one one element longer that sounds very wasteful and indeed it is so it's it's 50% costlier than necessary for long enough inputs in this case it's 370 against 320 it's not 50% yet but if you increase the size this is just a handful of elements so something's something's broken there and you can do it you can do it differently that works better that's uh what power sword

7:10 Introduction to Powersort

7:12 tries on the on the left is the code which looks very similar to Tim sworts code it's going through the list once it finds the next run it maintains a stack of runs that it still has to merge but the rule when and how stack uh runs on the stack are merged is different I think it's actually much easier each of the runs has a so-called power and you just maintain that the powers are increasing on the stack and if the new thing that you put on top is not increasing then you have to merge so I'll show you how this works what I don't show you on this slide is where these Powers come from there's a function here that says compute a magic number for this run and I'm not going to tell you what it what it does on this slide but on the next one so the way it works is you find the first run and you throw it on your stack and there's a a zero at the beginning that's kind of a a dummy value at the start you find the next run and you always have two runs in your hand you compute the power of the boundary between them powers are really just at the boundaries not the

8:30 runs then you throw this on the stack as long as this is increasing in power it's fine and you keep it now if you go on the next thing you put on top is not increasing two is smaller than three and that means something's wrong so you have to merge and you merge the the topmost things so these These are out of order the two is too big the the three is too big three has to go so you merge those two and the result of a run always inherits the smaller of the power and now everything is nicely in order again you go to the next step you'll find another run and again one is not bigger than two so the two has to go and we do that by another

9:23 merge okay uh from then on if you find the next boundary it has a power of two if you stick that on the stack is fine that's increasing two is bigger than one and one more is also bigger so nothing immediately happens but now we reach the end of the input and so from now on we just take the topmost two merge them and keep going until nothing's left j j

9:52 j uh and done so what I hope you can take from that example is if you have these blue numbers that are magically given to you it's very easy to decide what to do you just have to check if the new thing that you put on top of the stack is bigger than what you have there or not and you do this in the lube so as long as the topmost thing is is too small you keep

10:20 Balanced tree intuition

10:22 merging now where these Powers come from I'll I'll motivate with some animation so uh pay close attention uh top down merge sord is good because the merge tree is balanced that's the essential part that makes it effective so we'll try to mimic this the problem is that we can't use uh a topmost cut like this if it's in the middle of a run so we have to somehow round our our merge tree to use these these cuts that are that are there but we'll take inspiration from that green tree so the green tree is what we would do with top down word sort but we don't want to do it exactly like that so instead we uh we take the midpoints of the runs middle of that run middle of that run and you imagine they are connected by a line and then you let these lines fall down until they are stuck on some of those green poles so you take the green green tree to stop those blue lines from falling down uh let me just show it one more time so you get the visuals but yeah where do the numbers now come from they are just the depth of these nodes um in in the green tree so that's the root it has h plus

11:45 one it is at at level one so that boundary gets power one and the next two the children of the root these have two so they're giving power two to these runs and what this does is it it imposes an overall balanced tree that a boundary that is essentially in the middle is will get power one and that's a good last merge uh but it does this taking into account where the actual boundaries are all right uh so that's that's the power definition um if you pull the tree straight so that it it aligns with the boundaries then it looks a bit more like the trees we had before and that's the merges that you would that you would do so uh now you may wonder how this connects to the left to right version in timsort um but you can show that the the merges that timsort does when walking through the array and does doing this stack is exactly what happens here so you're you're never explicitly building the tree you're just uh internally using it as a as a virtual tree

13:05 there are many other ways to Define numbers that have some properties like this a global balance the the good thing about defining in defining them in the way we did it here is that this is a local property it doesn't depend on any of the other runs it only depends on the two runs where we take the middle point off and where they are in the overall picture it doesn't look at what the other runs are like

13:30 uh and if you want to know the details this is how you compute Powers I'm not even sure I want to uh explain it in more detail it's uh exploiting that you can you can approximate this screen Tree by cutting things in half repeatedly and cutting things in half repeatedly is something you can do with uh dividing by powers of two and checking U the binary binary representation of numbers um that part is not so hard to figure out but it's quite annoying to explain so I I'll just leave it with the code um and the intuition of this of These Bars sinking

14:19 Conclusion of Powersort

14:21 down uh to wrap up um first of all Power sword is is a replacement for one part in timsort namely the merge policy that part that decides when and in what order to merge runs all of the other things where the code for Tim sword works well is not changed so that's all kept and that's the locality of reference it's not having recursion which is is useful for space uh and some other tricks like the uh Galloping merges um but unlike timsort original policy you have a approvable upper bound on on this merge cost that's close to h h plus 2 N um and like Tim sword it costs almost nothing to determine these Powers so it's cheap to