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

0:00 <Untitled Chapter 1>

0:03 so in in this subsection i want to talk about the sorting algorithm in python's library and it's called list sort because it's uh it's part of the list objects um but it's it's uh probably used on a little more more widely scaled

0:17 Sorting in Python

0:22 let me lose a few words about python first just to make the statements that will come up a bit more precise if you talk about python itself that's just a specification it's a it's a long document telling you how a certain programming language of this name is supposed to behave but this is not really something you can run it's just a document telling you how it should run then to complement that because that wouldn't be much use the python foundation maintains a reference implementation so it's it's their implementation where they say wherever the specification might be not clear or leave some leeway or so on here's a reference implementation that should clarify this up and also shows you that it is possible to implement it in a reasonable way and this is called c python because it's written in c

1:16 so by and large if you run python on a computer where it was installed it is usually c python unless you specifically do something else there are some other implementations of python especially pi pi is another interesting one and there's a few more which are not very well known and most of them apart from these two are not as generic in that they don't support all the libraries that make python so great i think a large part of why python is so popular is that it has really really good libraries and usually open source ones for all sorts of things the language itself might or might not be your favorite it's maybe not mine but it has really good libraries um part of part of the python language specification really is a built-in function is the sort function on a list or the sorted building you probably know the difference but just in case if you have a list and say dot sort then the list is modified remember a list is a mutable object so you can change the value and sort sorts the list which is often what you want because it means you don't necessarily spend extra space there's also the sorted function where you pass a list as a as a parameter and

2:34 then it returns a copy of the list which is sorted that's the difference so when you need a copy sorted is more convenient sort is usually more efficient because these are part of the part of the language they're implemented in c and the algorithm that list sword uses is called tim sword named after the inventor tim peters and is exactly 20 years ago i think now yeah it's you can think of it as a way of merge sword with some twists to it and i'll show you a bit of these twists some of these twists on the next slide but i will leave out many other twists

3:18 and now since last september at least in the alpha version of c python it actually uses our power sword instead of some parts of tim sword so i was really excited to learn this it took in a sense three years to get from from that paper into some production code and here's a little comment um just from well yeah tim peters himself put the the code together in the end and decided after he got very interested in playing with this uh and experimenting with different options and at the end uh settled for this one i thought you you appreciate knowing this so python 311 is not is still in alpha so you wouldn't really run it now unless you install unstable development releases but it will probably be released at some point i think it's in the fifth alpha or so it probably goes through some beta it can only be a few few more years

4:17 all right so um this is this is my attempt to show the other end of the spectrum we've talked about the very simple algorithms like merge sort quicksort like like you have them in in textbooks and this is the other end of the spectrum that's what's running in a concrete library and one of the most widely used ones uh i guess the slide is a little scary so i should have probably hidden this part first

4:34 Timsort (original version)

4:43 in essence tim sword is a weird way to do merge sword left to right it's neither top down nor bottom up it's a third way which is distinctively different but has some benefits

5:00 it works by maintaining a stack of runs and so it nicely fits into this topic with runs and so it always works by finding the next run from the current position so it extends uh finds the next run and puts that on top of the stack now so far it sounds a little similar to bottom-up merge sort but remember in bottom-up merge sort we used a queue and we always paired up things as they arrived in the same order and always pairs all the way back and this didn't really work so well which is something that tim peters realized so instead he uses a different way so he puts the runs on the stack so the top most is the most recent that you just discovered and then there's a set of rules that tells you what to do and i think these rules are still somewhat magic that they work at all i will see that they don't always work that great indeed but that's something that was just discovered a few years ago

6:10 and yeah in tim peter's own words these rules were the first thing he discovered that didn't obviously suck so he stuck with them but they're indeed not the most thoughtful part of tim sword

6:25 so just to briefly explain how these rules work they only ever look at the four topmost elements in the run stack and they only look at the length of these runs so if this says z greater x it means the topmost run is longer than this third one and if that's the case it happens to be a good thing to merge the second and third why again maybe not completely clear at this stage and there's a few other rules so you always check them one by one if a doesn't apply if this is not the case then you try this one if that applies you do this merge if not you go on and you need all these four rules uh what they intuitively try to achieve is that the runs on the stack are exponentially decreasing in length the top most should be the smallest and then they always grow by a constant factor roughly

7:18 but that alone is is not quite good enough people like this for for various reasons but one of the reasons why why it's good first of all it picks up existing runs as the other methods um and secondly it has good locality of reference in the sense that you usually merge small runs often and you usually merge those early when they arrive on the stack which is just after they've been discovered so these elements are still fresh in your cache and then you merge merge them quite a few times before you move on that's one of the things that um that tim sword does well and maybe slightly better than other methods

8:08 i should point out that this this is the core of the algorithm to the extent that i need you to to see it to make sense of the rest uh there's many other parts um maybe i can just mention a few things uh if you find that the next run is really really small you actually don't stop there but you extend it to some minimum size and that is done with some binary insertion algorithm because that happens to be more efficient if you have very small lists another thing is that when you merge runs this doesn't do the standard merge all the time it sometimes does what's called a galloping merge where um you sometimes save comparisons if the input is is again structured in a certain way and a few other tricks of this type but they're not as relevant that they haven't changed last september it's just this this part that we'll look at now but the yeah the the core version is as given here you find the next run put it on the stack apply certain rules to maybe merge some parts and then move on to the next run detection

9:23 and let me show you a case where the rules in timstor don't work really great they still work okayish but not great um that's this this input where you notice the runs have all length one two or three and there's a peculiar pattern in the run lengths which means that our lower bound from before this h is roughly 316 and if you run peak sort on this it gets close to that uh but tim sword does what you see here um and i want to highlight that there's a few specific merges that seem just not very smart and somehow you can with this input repeatedly trigger tim sword to do this not so smart move and the not so smart move is for example here you merge a fairly long run with a single element into a just one bigger run so you you pay this this whole cost of reading the long run again just to make the run one longer that sounds like what you don't want to do if you minimize merge cost and there's there's ways to do it so i didn't put the tree for pixar on it but it just doesn't do this there's no need to do it

10:43 uh and yeah the example gets more concrete more extreme if you increase the input size as methodically tim's or does 50 more merges more merge costs than necessary all right so

11:00 where these merge rules are really not that great the rest of tim sword is really nice and people like it so we would like to keep this left to right structure in merge sort with a run stack but we would like to replace these these weird four rules with something more principled and that's uh what we did with power sword the structure is is still roughly the same uh the what has changed is we always look at the topmost two runs in in one go otherwise it's similar you walk through the list detect a new run put them on the stack and merge some things

11:43 let me walk you through the example and i will leave out one co well one key part which is the computation here of the power of two runs and how the power is computed you will see on the next slide on the bottom here you see the resulting tree how it merges things up at the end and i put this here so that you can keep track of what's going whereas uh what's really happening is shown up here so this is the current state of the array of the array it has certain runs again the algorithm doesn't see those yet it has to find them one after the other and there will be a run stack popping up here

12:39 and i'll tell you how to compute powers in the next on the next slide we start by finding the first two runs not just one and we compute a magic number the power of those two runs or rather the power of the split between those two runs and in this case happens to be three more on that next on the next slide and now you keep a run a stack of runs where you also store the power and the rule for the for the stack of runs is it's fine if the stack increases in power and if not you have to merge so that's what that says here if the new power that you computed is smaller than the topmost on the stack you have to merge the topmost two elements of the stack here we only have a single run so there can't be a violation so let's move on to the next one so those two the magic number turns out to be two so we put this on the stack but this is a violation because two is smaller than three so we have to merge those two these two which happen to be these two and we replace them with their result with the merge of a and b and you see it inherits the the smaller

13:59 of the powers that's how we can get back to the invariant okay in the next step we find these two runs and their power is one so a similar thing happens we put this on the stack but it's in violation so we immediately have to merge and then we get these three now let me point out when we merged before so what we merge here is is this node

14:36 right we merge those two runs and similarly here when we merge that's this run this this node in the merge tree okay then we move on to the next stack so so here the run invariant is maintained there's only one run so we go to the next one the magic number is two so we put it on the stack and this times it's fine it's going up if you move up the stack and one more time and then we are at the end of the array so we go into this last part where we just merge top down the topmost two until we only have one run and so this first merge again is this node then we merge the next two which is this node and finally we merge the last two which is the root okay so if you if you paid attention uh we did this one first then this one then this one then this one then this one

15:48 but it's a little easy to lose the the order in the animation is it clear how this works if you have these blue numbers magically given you just put the next run on the stack and if that new run has a smaller power you merge the topmost and once that's no longer happening you move to the next run

16:15 the the key thing now is how you compute these powers and that's a little mysterious if you don't know the theory of these optimal binary search trees behind it but i did want to put the code how to do it on the slide um i'm not sure if it's if it's worthwhile going through the details of the code really a more graphical way to represent it is is as here let's maybe take the these first two runs as an example so that was the first the first two runs that powersort looked at you take those two runs and now you can you take you compute this blue interval which starts from the midpoint of the first run and ends with the midpoint of the second run so middle of this one middle of this run that's this blue this blue little line and now i start at the top i go this is my entire array it has a midpoint at one half so if left endpoint is zero right endpoint is one one-half is in the middle i can ask is this point one-half contained in this blue interval no it's not it's far to the right so i have to continue to the next level at this point i divide it into quarters

16:16 Powersort-Computing powers

17:30 is any of the quarters inside my blue interval yes or no no again the smallest is still to the right so i have to go one level down now i take eighths and here i find that one eighth is actually contained in this blue part and so on the first lev on the third level i have one of these red ticks inside the blue interval that's why the power is three and similarly for the others if you pick any of the other blue ones this one came out as one because the one half point is contained in this if you go to this last one that's a very small one so not even the the third one was contained but the 15 over 16 one was contained so it gets a power of four i know this looks a bit uh mysterious why this is a good idea and i don't want to go into the details but there's a way to make this very intuitive it just takes more time

18:32 this was the tree again that we followed with the merges and so you notice you can you can put the root at one that splits the thing into the left and the right part and then you pick the next one that's highest up and you keep splitting like this that's how you can get the tree

18:52 and there's another way to visualize this if you if you put these blue bars you put the highest in the middle and then between the left boundary right boundary and middle you put two bars of one height less and then in each of the resulting segments you put one bar more so you you put these four ones in um that gives you another way to to see so you could imagine having these these light blue bars stack up and then you let the the dark blue interval sink down and they will stop whenever they hit the first of these poles it's just another way to visualize the same thing

19:39 uh so let me wrap this up again so i think the the details of these last two slides 35 and 36. this shouldn't pop up in the exam just because this is uh detailed stuff from from my research uh but uh is it's a lovely topic so you're very welcome to dig into it but yeah it won't it won't be on on the exam other than the abstract idea

19:49 Powersort - Discussion

20:18 what's good about powersort is that it retains all the advantages of tim sword you can take all the indeed the same code and just replace part of it in particular you still have this good locality of memory accesses um you don't need recursion it's another thing that is nice in tim sword you don't have to rely on the recursive call stack

20:43 you can again prove merge cost is i've said this before but it's a while ago we have this lower bound h and we have the plus 2n that you sometimes need and you never need more in powersort same as for peaksort and finding the order to merge runs has minimal overhead i didn't talk about the code here but you can even replace this loop with um bit tricks so it's constant time even on word ram magic so it's very low overhead and also very low overhead in practice