Video 3-5: §3.5 Adaptive sorting & Peeksort

0:00 Introduction to adaptive sorting

0:04 in part two of the Sorting unit we'll look at algorithms that try to be a little smarter when they can and um smart means they can exploit if the input is is friendly to them to sort faster and we'll slowly make our way there um to in the end look at what the current sorting algorithm in in Python is using and you may know I had some some role to play in this we'll come to that a bit but I want to motivate first from from first principles what this is

0:40 about adaptive sorting is the idea that you try to exploit order in the input that's already there now the comparison based lower bound that I showed you in in section 33 uh the way I formulated it was for the worst case but you can actually do the same argument and get a Bound for the average case and um just uh if you if you have this fresh in your head every algorithm that's comparison based is essentially a comparison tree and we argued about that tree needs to have anoral leaves to distinguish all possible input orderings and then it needs to have log of n factoral in height well actually it also has almost all leaves at that height at least it can have some leaves higher up but half of the leaves will be at that depth or some something like that uh so you can prove that the same bound also holds in in the average case so what this means is on most inputs if you have a random input randomly permuted input there's no way for you to exploit anything because if uh if we have full Randomness those that number of comparisons are necessary and remember this

1:57 is ASM totically equivalent to n log n and so either quicksort or merge swort will essentially do this um but even in the best case they use this n log n number of comparisons so usually we can't do much better but uh it turns out that uh what people sort in practice often Isn't So

2:25 Random so you could ask can we do better if we're in some sense almost sorted and this could happen for example um if you have data that arrives over time and you occasionally want to sort it so you have a sorted prefix then you append new somewhat random data and then you sort the entire list again now you could do you could try to do this smarter but uh with python there's no need to you can just call sort on the entire list and it will be as fast as doing some custom made sort the last part and merge the two or so also if you do um um if you use sorting to do a statistics of some time series and the time series is say a temperature measurement you won't jump randomly around it will be somewhat smooth if the time steps are not too big uh if you uh if you have data that comes from various sources and is roughly ordered but then you merge those you might write a specific merge method that does this cleverly but you might also just concatenate them and call sort in Python is essentially the same speed so some of these scenarios could be solved differently but people started to not not do it because it works so well

3:38 with the Sorting method so the the goal for the algorithm would be to adapt to the input the the more it's sorted the faster it should become that sounds great right uh but how could you possibly build something like this how could this work let's start with a stupid simple idea uh what if before we sort something we check ah is it already sorted and if so we don't sort it that obviously uh Works in that the best case is now just checking that the thing is sorted that's the minimum you you definitely need to spend any sorting algorithm that should be correct has to check that the input is sorted if if it is uh but of course this is only one special case so it sounds like a a fairly useless idea but remember that our our key sorting algorithms both quick sort and Mer sord are essentially recursive so if we do the same trick in every recursive call we might pick up things much earlier and this idea is is as simple as it is it it gets you quite a a good way towards a good solution um it's good enough to exploit some some some ways of presorted it's the key idea that we'll exploit but there's a few things that um are problem

3:41 Simple sorting optimizations

5:00 get so we'll still have to refine it um in particular if you do a linear amount of comparisons at the beginning of every recursive step you're by and large uh if if the uh input is not random you're basically doubling your cost or worse and so um maybe that point here should be refined to the more sorted the input is the faster the algorithm should become but if there's nothing to exploit the algorithm shouldn't be much slower than what it could have achieved otherwise you you don't want to degrade the performance on the the average case just to buy yourself a small advantage in some some Corner cases so that's that's the challenge in this U now it turns out for merge sort you don't have to check the entire input is sorted you can do something much cheaper after the f after the two recursive calls so remember that was merge sword which just find the middle by index arithmetic sort the left half recursively sort the right half recursively and then there's a single comparison that I can do if everything in the left half happens to be smaller than everything in the right

6:19 half I can check with one comparison if the entire input is sorted and that's super cheap that's definitely worth while doing also if that comparison comes out as as not smaller then you have to do some some work so it seems like this is just as good as checking the entire thing for sorted okay let's keep that idea and see how far we get with

6:44 Analyzing performance metrics

6:46 it much of what I'll show you now could be uh stated more formally as as proper theorems to show you exactly what's possible and what not uh but I decided to instead keep some indicative examples that show you what happens yeah the numbers are really small doesn't matter too much uh what you should see here is there's runs which means sorted pieces that are already in order and let draw it a bit more carefully so the the numbers the last numbers are the smallest and then these are all up here these are up here and these are in into my text that's the numbers okay so that's that's my first example input we have 64 numbers but they're actually sorted chunks of length 16 each what would standard merge sort do of course uh so the change here is that we don't really the algorithm doesn't know that these are ordered in that way if it wants to exploit this it has to find out what would standard merge sword do standard merge sword would start with the entire list then recurse on the left half oh and that actually recurses on the left half recurses on the left half recurses on the left half all the way down until it has two individual elements and then what it does is it

8:11 merges those two elements into this little sorted part of two elements okay once it has done this on these other two ch ch chuk it will take those two runs of length two and merge them to one run of length four and similar for all the other pieces that's standard merge sort if it doesn't do the sorted check if you study this carefully look at the numbers and remove everything where the two runs are already in order you get that all of those merges that are grayed out you don't have to do because in each of those cases let's pick out this example here um there's 53 and 54 so they're already in the the right order so you don't have to touch them uh if you pick out one higher up then again um the left half is already sorted so the rightmost element here is this uh 56 and the right half is also already sorted and 57 is bigger than 56 so again it's already sorted we don't have to do anything all right uh what I put down here is um the merge cost of these two variants that's a useful a useful metric that's a little simpler to analyze than comparisons because for comparisons if we remember how merging worked it

9:42 depends on which run is exhausted first how many comparisons you need in detail uh and that can be a bit misleading also the algorithm still has to has to produce this merged output so you could pretend U merge cost is the size of the two merges which is the number of rides that you have to do and so if standard merch s in this case needed 380 we now are down to a third of that so that sounds like it works pretty well right now of course this example was chosen so that it works well and um uh we'll see another example soon but let's try to analyze this a bit more General this was just one one concrete example if you look at what happened in the previous example we had a sorted length a sorted run of this length and basically what we saved is sorting that thing so if we sort with merge sort something of length L that has effort that costs us L time log l merge cost and comparisons so that would be exactly the cost of creating this with merge sort if we if we had to sort it so in a in a sense that's the perfect phase we we saved exactly what we would have had to spend to sort that part if

11:07 we call merge sword just on that Subs segment and so um we could take the overall cost of standard merge sword ignoring the sorted and subtract the best possible thing we could save and what's the best possible thing we take the length of all the runs so L1 L2 L3 and so on that's the length of these already sorted segments and we subtract Li log Li for each of the runs that's the best we can hope for so we'll we'll call this I I'll call this age because has some labor that looks like an entropy but you can ignore that uh it's just a it's just a letter to uh denote it somehow in a way that's the best possible we can hope for so there's no there's no uh reason why merge sword would ever save more than that so it's kind of a lower Bound for us and if you um if you look at a a different example uh so here you have again four runs and 64 elements in total but the lengths of the runs is is slightly shorter two 15 and then 2 * 17 standard merge sword is the same as before this age value is almost the same as before remember it was 128 when you had uh the previous slide all runs of

12:30 16 uh and what happens if you call our merge sort that does this sorted check is is something like this uh it profits at some part but then there's all these cases where the Run boundary overlaps in some sense this part of the input it can't uh profit from the sorted so we're only realizing half of the savings uh which sounds sounds maybe not so great all right maybe we need a different idea let's try a different variant of merge sword um I'm not sure if if people have seen bottomup merge sword it's it's a variant that's a little less known than the standard recursive one uh the basic idea is to do instead of a recursive recursive step you work yourself from smaller runs to longer runs um let me explain the code briefly and then uh we can we can look at an example so at each at each step we have a queue of runs that we have to merge and initially we say okay I don't know anything so the runs I have to merge are individual

13:00 Bottom-up merge sort

14:00 elements and uh then in the next phase I always go through my queue and I take the first two elements which are runs and I merge those and store that in their queue for the next round okay so in the round

14:18 one I would take the first two and merge those and remember this so I I create a new queue I take two elements out of the old que and merge those and I put the uh I put the result into the new que the Q prime or q and Q is could be the letter or the word q so you'll have to uh insert the right meaning uh so we we go through this as long as we have Pairs and um then we uh swap the roles of Q and Q Prime if you want so in round one we take Pairs and uh merge

15:11 them now we have runs of length two in the next round we take again go through the que and just take the first two and merge them so we'll have runs of length four and then at round three we're done if we have uh eight elements initially

15:34 okay now why am I telling you this uh is is one other way to do merge sword why is this useful if you uh if you look at how we initialize the queue we're going through the list and decide every element you run of your own and there's no reason to do that we could instead uh just scan forward and check how long are things increasing so um I'm move through the array once I keep track of the end point of the next run and uh while that is increasing so while the next element is bigger than the previous I just increment that and inq the run that I find that way for those reading the code carefully there's a a boundary check missing you somehow have to check that J doesn't run past n so you can imagine that there's some um um Sentinel value that stops that from happening minus infinity I

16:41 guess that's just to keep the code on one slide otherwise I it wouldn't have had this nice correspondence so we only change phase one we initialize the que differently by scanning through the input and finding sorted segments all the rest is grayed out because it's unchanged that's pretty smart right now we did detected exactly the the sord it runs in the input so that should do much better uh let's see if um if you followed this rule so here's

17:15 Limitations of current approaches

17:20 um suppose we run the uh standard bottomup merge sword not the one that tries to find sorted segments that's why I gave you letters suppose they're not not ordered all already so the standard bottomup merge sword uh in which way would it split those five elements and it might be better to try to get both on the screen

18:45 many people have cast their vote some people are still typing or thinking right so let's see what's you got this got this right um let's briefly go over it so why is it the the first outcome the first policy we go through our cu in the same order and we don't look at how long the runs are so in this first round we merge these two then these two and then there's this last element um which is the lonely Run Part here so whenever we have an odd number of runs we'll just leave the last one lonely and copy it over to the to the next queue and so that's what happens here all the time we merge the first two and then the third is again lonely only in the very last step it gets merged um policy two is standard top- down merge sord and policy three is the same if you round up instead of round down uh right good so um if we do our smart bottomup merge sort where we detect the runs uh this is what happens uh this is again just repetition from before that was how top down merge sort with the sorted checked it same picture from before and as comparison the bottom up one so it it immediately

20:35 finds Those runs so it doesn't even recurse all the way down to individual elements um and it merges those those up and achieves cost that is close to AG this lower bound of what we could possibly wish for uh and so it looks pretty good now unfortunately uh it also has it's its problems and the example from the slido question alludes to that a little bit bottomup merge sword is uh not at all adaptive it just merges things as they come along independent or irrespective of how big they are and that's not a smart idea if you have an input like this then our our bottomup merge sort would treat this very long run that it finds in the input the same as all these short runs and so over and over and over again it repeats merges with this long run and that's just driving up cost uh where's our top down merge sword with the check didn't do that or it wouldn't do that it does some more interesting things on the right but then this long run is only merged once okay H so it it looks like both of the approaches taking simple variant of merge sword don't quite always work they both have their cases where they're fine but then others where they're not so

22:08 effective it would be lovely to have one method that does it all so at this point it's it's useful to maybe uh pause a bit and ask what do we actually need both of these Solutions came from simple hacks or or changes to existing merge sord variance maybe that's not exactly the right way to go and conceptually I think you can split this uh there's two tasks we have to somehow find inputs if we want to use them we have to detect the uh we have to detect runs in the input and that gives us the lengths of these runs uh and then in the Second Step though we have to somehow determine in what order we want to merge those and uh This was done this was dictated by the code in both of the cases bottom up didn't at all look at the Run lengths it just merged them up by pairs and top down did this somehow automatically from the recursion without much explicit thinking so let's do the explicit thinking though um I I'll I'll draw this this kind of diagram a few times so um you've seen it in the examples before uh this is a merg tree it just means that you take two runs and you produce the merged

22:10 Optimal merging strategies

23:24 result of merging the two children and you can repeatedly do this so you merge those two input runs and you produce a run here and then you can merge another input run into those this intermediate result and obtain a longer input run so uh any kind of possible merging order is a binary tree over the runs that's what um what you can observe here and also the total cost is just summing up the gray area why is that uh if you have an element like the 20 how often does it play in a merge well we pay for this this run when we produce that result and we pay another time when we have this result and that's all so whenever we write an element we pay for

24:23 it now you can re you can uh Express this cost in a in a slightly different way you can also say I'm not looking at these um these long lines but instead I'm counting every element how deep it

24:41 is so if if number eight is in a leaf at depth 1 two 3 it's merged three times so number eight should contribute a cost of three to the total so I could also sum the length of all the paths from the root to each of the elements in the leaves that's the same as the sum of the gray

25:04 areas and because the leaves are all at the same depth you can say it's the number of element in the leaf times the depth and you sum this up over all leaves why are we doing this it turns out that this this quantity has a name it's called the external path length of this binary tree um and that connects it to a well studied problem the problem of finding the optimal binary search trees I sometimes people see this as a as an example for dynamic programming algorithms in in some algorithms class this is a special case of it but um doesn't matter too much um the important bit is there's there's known algorithms to find the best possible such tree so you can take any such algorithm and and plug it in to do this step

26:00 two uh what I did 5 years ago uh when I was a postar um in in waterl in Canada so we we made that observation of this connection and found some uh not exactly optimal algorithms because those are slow instead something that gives you a a tree that's almost as good as optimal nearly optimal um there's several such in in the literature not all Mak sense for turning them into a sorting algorithm but two did and those lead to these two algorithms that we'll briefly discuss and and you can prove that they are never far away from this from this uh quantity age that I introduced earlier that the best possible case you can hope for uh and they're very quick to do so they don't need a lot of extra time I want to show you the one that nobody uses first because that one is easier to explain and I think it's kind of of underappreciated it's a very nice algorithm uh but there you go it's called Peak sword uh the reason it's easier is because it's it's a slight Twist on top- down merge sword not much changes uh but instead of top down merge sword just cuts the array in the middle and then you recurse uh instead Peak sword looks at the middle and tries to

27:02 Peak sort and conclusion

27:21 find run boundaries so what that means is um you treat the whole array as the interval 0 to 1 then you find the mark 1/2 and you start scanning in both directions scanning means from this point you try to find things going down from this point you find things going up so you find the middle run the one that contains this half mark uh so you have two possible split points if you want to keep that run where it is and you do this maybe natural thing you take the split point that is closer to the 1/2

28:05 part so this one's closer so we cut here and that becomes the last merge we'll ever do will be that part and that part but it's top down recursive so you don't see this you just have that implicit in the recursion same as standard merge sord but uh you just choose a different point to

28:27 cut it's a recursive algorithm so you do the same in the left and right sub trees again you find from the Middle Run you find uh the two boundaries and the one that's closer to one2 is where you cut do that on the right side as well and if you keep keep going like this uh you naturally stop at a run because say in this left run in this left recursive call you jump in the middle and you scan until you find the Run boundaries but then you you notice oh it's actually my entire input so I don't need to do anything and the same happens for for all those other um leaves and when you come back you just merge as in top down merge

29:11 sort uh you can do um you can do it essentially like this if you want to be a little smart you want to avoid scanning long runs several times you spent the comparisons to uh detect the runs so you don't want to do that over and over again so um by remembering so a normal recursive call from mer would say you sort recursively from L to R some range in the array uh we initi We additionally have to remember if there are detected runs on either side we remember how long they are if you do that then you can do a clever recursion I know this looks uh looks wild but um it's not actually a complicated code it's just a few steps of

29:58 arithmetic so the the whole the whole whole trickery is just keeping track of this length of left and right runs that you've already seen to not detect them again so you have a bunch of cases that I tried to simplify into a into one one case by doing the case distinctions inside the computation of the parameters if you want to understand why this works you may want to do an example um I just wanted to have code that fits on one slide to convince you this is not not so complicated and the concept actually it's easy right all you do is find the Middle Run and take the closer cut Point um doing that a bit smart is messy

30:45 pardon the Middle Run is what whatever you find you start in the middle of the array and you scan left and right so you you always get this one

30:59 well that's it's another parameter so the recursion has four parameters a range and two numbers which are lengths of runs on either side that you already know are runs and they could be

31:17 zero so these elements in here uh these are just arbitrary you don't know anything about them so the the recursive call means this is ordered and this is ordered but in between it can be whatever you don't know

31:37 yet yeah basically yes but you do this recursively so what you what you do in in pictures you know this um you find another third run in the middle um and you find the closer cut point and then you recurse so in that left recursive call you again have known runs on both sides in the right recursive call you only have one on the right side and then there's different cases the annoying bit is ah it could be that the known run on the left is actually overlapping the middle point then you want to not scan that again so this a a few annoying Corner cases that's why you have these if statements

32:26 here yeah and initially you called it like this um as I said this code hasn't really found as much use so I don't want to spend too much time on it is H you're fine if you keep keep that abstract idea in mind that's all we need uh the code so this slide is just my proof of concept that it fits on one

32:49 slide uh I wanted to show the same example we had before where both of the algorithms didn't do so well um so in particular here's the comparison with the bottom up merge sword did really poorly on this one because it has one long run and then many short ones and the standard merge sword with the sorted checked a bit better but you see AG is quite far away from that still and and Peak sword gets very close so it looks like we can have the best of both

33:23 worlds this is one concrete input you can't really Define astics for one input right the complexity of of this overall thing is H + 2 N and whatever H is H can be between linear and N log n so um I guess it can be between zero and N log n

34:02 and it depends on the input what H is as I said before there's no hope if your input is random H will be roughly n log n and no possible algorithm can can exploit anything if there's nothing to exploit but if the input has the structure of many long runs then the algorithm will will pick it up