Video 3-7: §3.5 Adaptive sorting & Peeksort

0:00 Intro

0:03 and in the second part of the Sorting units we'll look at ways to be a little Optima opportunistic if you like if the input has already some partial sortedness a good sorting algorithm should try to make take advantage of that and and we'll call that adaptive sorting as well

0:29 Adaptive sorting

0:32 Let's uh let's start from from first principles on this in a way remember we're back to the comparison based model just because it's it gives us versatile algorithms if it's comparison based you can apply it to anything that you saw it there's nothing more General if you can sort at all you can sort it with comparisons uh other things might take advantage of say the objects being integers but the the most versatile algorithms are comparison based so we like that model which means we we can't possibly beat this lower Bound in the worst case uh even more if you if you analyze these comparison trees more closely you can also show that uh it's not just that the longest route to Leaf path has this length it's actually the average length as well you can't have most elements higher up that gives you the same contradiction so this lower bound I've shown you based on the comparison trees also gives you the same virtually the same bound rounded down instead of rounded up for the average case so it seems if you pick if you pick some random inputs random in the sense of randomly is shuffled then this is the the cost you will have to pay uh quicksort and merge sort um are are close to that in the average

1:59 case but even in the best case they still use n log n that basically follows from their divide and concrete nature it's uh at least in time so um there were the the code that I've shown you will not get faster even if the input is is very easy

2:24 so you could think about if we can do anything about that uh what can we do if the input is already almost sorted uh oh and what does that that actually mean there's different ways how you can formalize this but it's instead of um starting from definitions I want to show you some example applications why why it naturally arises in some cases that you're you want to sort something but it's not completely random uh one one thing can be it is basically merging different data sources where each of those has a natural tendency to be sorted for example log files from different servers and you want to collate those there will be some sordidness or uh they're almost sorted but then if you take them together you have to somehow bring merge merge them in a way uh another application it could be if you if you have a Time series some sensor data that you measure I usually say a temperature sensor it doesn't jump too much in short time increments um and so there's some way of a dependency on time it might not be that it's completely sorted right it might go up and down but there's some some local sordidness in such data

3:48 um kind of the the similar similar Point as the first one but framed in a different way or in a different application uh things like um distributed computing Frameworks that that there's well without going into any detail of these uh they often work by bringing together data from different sources because they're they're distributed across different computers and so you have to bring them back into one one collated thing which often means sorting question yeah um to answer the question you said about like um like my five different bits like instead of like searching individual elements if you saw some sorted it is like he could yep

4:42 chunks that already continuous chunks already sorted pictures of an individual perimeter yeah okay so um the suggestion was to take take sorted chunks and use those as the basis of sorting that's what we'll do uh you will see there's there's some uh there's some subtleties in doing that um there's other ways how you could Define pre-sortedness it's basically a vague term you could you could come up with whatever definition of that you could also say there's is all is sorted with few elements that you only have to move but um I think from these applications what you suggest is is most natural there are local chunks that are already in order so let's let's try to exploit that bit

5:36 Warmup: check for sorted inputs

5:39 so how could we do this uh a very simple way would be if the input is completely sorted already we don't have to do anything so we could check for that case I mean it's fairly cheap this compared to n log n n minus 1 comparisons is not so much but of course is very limited right you only get the completely sorted case fine maybe you can add a second special case for the reversely sorted one and do you want to keep going like add more of these questions

6:47 so instead of like can't you read that one special with candle all kids where they are so stupid they are stronger okay so the suggestion is to kind of while you check if it's completely sorted if the something is not sorted you kind of put it in another bucket in some way or another um I think most methods do something like this the the trick usually is you want to do it all of this in a way like a I always phrase it like this you come up with some super clever scenario to etch out some some cases uh but then by the time you figure out what to do quicksort says oh I'm done by the way you need to do something really really low overhead um and um I'm not saying this is not the way to go but you you need to be really careful about not causing a lot of extra effort before you keep keep going with before you get going with the Sorting okay so this was this was just like uh that's that's not a sensible suggestion right this is uh as a first very simple thing to do you can check if you're already done and then stop but that's very specific now the algorithms we've seen I didn't

8:01 stress that point too much but you may have heard of dividing concrete I touched on this at the beginning a bit the algorithms we have see in quicksort merch store they all are recursive so they could do this kind of step in each recursive sub call and then suddenly the whole idea becomes a little more interesting because you're not only capturing this the whole thing is already sorted but some sub-range that you recurse on is sorted so you could stop at that point in the recursion tree so that's that's a little better the thing is if you could repeatedly check for sordidness and do this at every level you're at least doubling the cost or something like that you add overhead that is is on the order of what you pay for sorting so that's probably going to be like what I said before right you you keep going like this you're very happy that you could skip a few subtrees but you're halfway through and quicksort says I'm done so we want to do this with less overhead and I don't think this is possible in a black box way but if we look at the two algorithms we've seen in more detail you may see that for merge sort we can do this much cheaper

9:21 merge sort has the nice feature it first sorts left and right half and then we come back and merge the two now if we're lucky everything in the left run is smaller than everything in the right run and we can find out whether that's the case with a single comparison just take the biggest in the left run and the smallest in the right run and compare them if they are already in order we don't need to do the merging step is already done this doesn't save the recursive calls unfortunately but we'll apply the same strategy in the recursive calls so they do still get cheaper if if there is um pre-sortedness in there so it's a very simple idea I think um and like you could you you naturally are left there from um a really bogus idea to something that that has uh has promised at least this is just copied the merge sort code from a couple of slides back with all the animations probably a couple of hundred slides back but there's only one one line added that's the comparison that I mentioned so how good is this uh

10:34 Mergesort with sorted check - Analysis

10:38 in in this subsection I don't want to go too too deep on the analysis so let's have a look at some indicative examples say what we'll uh look use at our as our cost measure is not the number of comparisons but something slightly simpler to analyze the merge cost so merge cost is just the size of the output of a merge by and large that's the same as the number of comparisons in the worst case but if you're merging sometimes you're lucky and you run out of one run and then the second the remainder of the second run you could just copy over without further comparisons so you would kind of always have to say oh at most and so this is inconvenient merge cost is always the same and if you want if you like that justification better merge cost is the effort to produce the output in the array you have to write the elements there you're copying them even if they were already from the same run you still have to copy them over to the buffer so that's just um to simplify the discussion if you like

11:47 is essentially the memory transfers that might be more expensive in practice anyways uh okay so here's a some input yeah it might be too small to read but you see that this is sorted up to this point and then the next two these are sorted and this is sorted and this is sorted I kept things very nice so it's a it's a power of two in total it's a power of two in in each um

12:15 so of course merge sort doesn't know this right it starts uh and doing it's doing its thing and here um I drew the recursion tree from merge sort where so merzer would start here and say let's split in the middle call too recursively two recursive calls for the left and right half what I also Drew is this vertical bar which is Just A visual representation for merge cost because that's the size of the output of this recursive call at the topmost level we at the End Produce in sorted order the entire list the left recursive call of this top call produces the left half and so on and so forth okay so another way of showing what merge sort did um but it's so far exactly what we discussed back then and you can just sum up the sizes of all these gray blobs and again you see nicely this is the same at each level they just fill up the entire space on each level so it's n the size times the height of this tree and that's log n because we keep cutting in half okay now if you sum this up for this concrete example you get this this number and if we do our our fancy new version with the sortedness check

13:34 it cuts that down to a third by basically stopping at this point right this this merge we would still have to do but at this point we're entirely within this sorted part I will call these sorted Parts runs as we used you use that term for merge sword when we discuss how merging works is that there's two runs and now we merge that into one one big sorted list so we could as well call this one run

14:09 okay it's on the slides um and this recursive call will not have to do anything it will start here call itself recursively on the left and the right half blah blah blah all the way down and then for these two individual elements it comes back and says oh I don't have to merge you guys you're already in order happy so it passes control back up same thing happens here control passes back up for the first four elements oh you're also in order so you keep going up if you look at the number of comparisons you pay it's a bit awkward to account for them because they happen at different levels in the recursion but you're really just using the minimal number of comparisons to find out that this is sorted anyways if you project down these these nodes you compare every two consecutive elements over the course of the recursive calls okay and so in this case this happens for all those so all of these I grayed out the bar because there's no merging happening so in terms of merge cost all these recursive calls are for free in terms of comparisons they're not exactly for free but they wouldn't cost and login they would cost n minus 1. so merge cost again ignores this so it's

15:28 a little easier to keep keep numbers good so far we like sortedness check yeah uh so that's that's a tough question the question was uh does this change the asymptotics or just the constant Factor and the answer is it depends on the input um simple answer to your question if the if the input is already sorted it does change the asymptotics because then it works out to do just n minus 1 comparisons and no merge cost at all so depending on the choice of the customer who's either for free or linear linear time as opposed to n log n what happens in between if you're if it's not entirely sorted but some bits are sorted it all depends on how much is sorted the detailed analysis for this concrete algorithm is a is a tiny little tricky and I'll show you why

16:39 Alignment issues

16:41 um okay I do have some some bits of the analysis let's let's do that first and pretend we're on the picture from before if if we have this nice scenario like before all runs are the same length say l in terms of merge cost not doing all these merges safe does exactly what merge sword would have used to sort those which would have been L log l so um we save the cost of creating this run if it already is sorted so we can say we take the overall number uh the overall merge cost of merge sort if there was no sortedness check if we subtract what we say which uh from in the good case of the slide before is exactly the length of the runs uh well l i Times log log of that because that's the cost merger would have needed to spend to create that run all right

17:46 um okay let's let's give this quantity a name okay if you have an input with run lengths L1 to LR then h of that of these links is just this uh this difference

18:02 now the um the the tricky bit with this is it works for the example on the previous slide that merge sort has exactly this cost uh it doesn't work in general so here I have the same kind of setup so it's again it's maybe a bit hard to see so here here are the Run boundaries if you have good eyes you may spot that this is not exactly splitting quarters instead it's this is one short or uh yeah so this is this is 15 and another 15 and then to 17 I guess so the total length is the same but the Run boundaries are slightly moved around and now you don't get exactly such a nice picture there's a few other recursive calls that need to merge and in a way for a stupid reason right this this call here would really have to just include one more element into its run but it doesn't know that so and it doesn't exploit that fact

19:03 and you see if you add up the numbers then uh this doesn't look quite as good as as we had it before intuitively you could say the Run boundary can cast this this Ray upwards and whenever that Ray crosses uh the merge merge node then you have to keep that and do the merge all right

19:27 um you can try to analyze this a little better that might be a nice student project um but now I would just leave it with that saying this would be great but the simple merge so we have so far doesn't always get there question

20:13 these kind of boundaries would be good for yeah since um three years ago or four years ago by now definitely yes okay I'll uh I'll show you how soon um there's one step in between so um if you see this it sounds just really stupid to insist on cutting things exactly in in half at each recursive call if that doesn't align with the with the Run boundaries we find we find in the input now that's definitely the cause of this overhead so let's let's try to get away from that uh and um so there's another way to do merge sorts that we may not have talked about so much uh but you'll uh so this is a slight hint for the tutorial question this this week has a lot of like uh fun puzzles um sorting with your your right hand tight on the back in a way uh and maybe this code will help um I don't want to spoil it by much more you can you can do merge sort bottom up instead of uh starting at the root with a recursive call and then cutting things in half you can start with individual elements and say okay my first task is instead of individual elements I'll make pairs that are sorted so I go first to sort them

21:45 all the way through and then you have everything paired up so that two consecutive elements are always sorted now you have runs of length 2 so you can take the first two runs each of two elements merge those into one run of length four if you spell that out that's that's what this code does so maybe let's um do a tiny example on uh just um say eight elements that's not eight

22:22 that's called bottom-up merge sort if you've seen this before maybe I should have said well the slide says so but as an and what's currently on the slide ignore this for now uh that will come on the next bit this is straight bottom-up merge sword with no no twists so you start out with treating each element as a single run of its own

22:45 the next round would take two of them and merge them so you end up with four runs of two elements each then you take again two of these runs and make them to runs of four I'm just drawing these boxes to show that these are in sorted order right you should fill in proper numbers and so on but you've seen my drawing skills so let's leave it with that and then the last point is turn that into one big sorted list no recursion no recursion needed you can do this you can organize that that process um for example in this way uh so you start with you keep a queue of things to do in this phase you initially put individual elements in the queue so what is in the queue formally is always start and end index of of runs this puts individual elements inside then you run through the queue you always take two elements out you merge them and you put them into a new queue for the next next phase so again if we look at what we did here so this is the queue initially we fill it with all the runs we take those two out produce the merge results and add that to a new queue we take the next two and add that behind

24:11 this and so on and so forth so you get exactly this this kind of pattern of merges yeah okay so this this will eventually terminate good you don't create a new queue the the standard mode is you keep creating a new queue which will have half as many runs and at some point you will have a queue with just the sorted list and in that case um uh you don't stop right so maybe this code needs fixing and to terminate I'll double check but the the key part is all right

25:19 yeah it it happily packs the full array into the new queue and keeps keeps looping uh apologies for that but it's it's easy to fix you just need a and another if um which might blow up the the size on the slide I tried to squeeze this already a bit uh the key point I want to get to here though is you don't need recursion and you don't need to split in the middle you can let this organically happen bottom up and so the insight for natural bottom-up merge sort is instead of starting with individual elements let's try to find the runs that are in the input and use those so that's that's what this does it finds the longest sorted segment starting at this point just keep going as long as the things are nicely increasing and then you keep put that in the queue instead of the individual elements that sounds pretty smart right

26:22 no I mean you you kind of maybe guess um what happens so if we look at the example that did not work so well with the top downward sword and sortedness check that was this example if we look at the same example with the new idea it works brilliantly because you detect this run you detect this run and this and this and you nicely merge them up so instead of paying this 216 you pay 128. which is very close to what we had was very close to this h quantity which was our kind of idealized goal if we could always perfectly save as much as merge sword would have had to spend to create that run that's that's intuitively best possible

27:19 this one the the h yeah yeah you can prove that this is a lower bound uh with some a little bit of a noise term but um by and large that's that's the lower bound definitely for merge cost

27:36 right so that sounds good now unfortunately there's another problem with this new method uh what if your input is like this one really long run and then a lot of noise at the end think about the log files maybe you keep a log file you sort this every day and then you append new random things why would you sort the log follow maybe some database you have updates at the end and you want at some point sort this for the next join operation uh so this this doesn't look too uh too made up to me to say it like uh carefully now our bottom-up merge sort has a problem it doesn't really take into account how long these runs are and so it will it will merge this really long run many many times which blows up the cost if you compare that again with our first method the top down we've sortedness check that seems to work much better here so we have two methods now neither of which is really satisfactory in both in all cases and I've just shown a few examples right you can maybe there's a third one where both are not so great so it seems somehow this is not really not really the solution

27:38 Natural Bottom-Up Mergesort - Analysis [2]

29:00 we would really like to have the good behavior in one single method and so um sometimes you can help to go back to first principles and think about what we want we like the idea of picking up existing runs

29:39 oh yeah yeah it's a good comment I'll repeat it for the recording that so what we intuitively want here is not mess around with this long run many more many times keep that separate sort the rest and then merge um very true the trick of course is uh where's the cutoff what if you have two fairly long runs it seems like this is an endless an endless game of uh special cases so what I thought at this point is let's let's go step back and see what we really want we liked the idea of picking up existing runs because that's after all what we're what we're trying to do exploit the sortedness that is there so we have to somehow find that and not just randomly stumble over it as the top down method but then these runs that we do find can have vastly different lengths and so it would be stupid to ignore that turned on its head we want a smart way to order the merges that we have to do and so uh this seemed to work well in the top-down method because it this this splitting in half made sure that the trees never get too tall and bottom up doesn't have this property so somehow uh we would like to get these

30:05 Good merge orders

30:58 two things so maybe instead of working from existing methods and tweaking them a little let's try to find a new method um just to make this um all right so this first step finding runs uh bottom of merch sort already did that right that's that's not our worry that's not hard the tricky bit is to find a good order of the merges in particular if they have uh weird patterns of length small long uh weirdly intermixed now uh any order of merges at the end of the day will look like this in other in other ways in other terms it is a binary tree

31:49 every merge replaces two two runs with a longer run and can itself be used in more merges so uh it's it's notes that have a left and a right child the first and the second run and it's also it also has this property that uh we don't want to merge say the first run and the very last one together in one step the reason for that is that we want to keep stability remember one of the selling points for merge sort was that it's stable if you have equal elements they stay in the relative order you can you can think about this if you have merges across uh if you have runs if you have elements in the middle and you merge these two no matter how you deal with them you will lose stability because you don't know what's in the middle you could move things to the front or to the back and both could both could break stability however if you always merge at Json runs you don't get this problem and these two things together mean all that we're looking at is find a good binary tree on top of these runs that uh that defines a good merge order and what's a good merge order it's one where if you sum up all the sizes of these of

33:07 these gray bars that's the minimal that's the cost and we want to minimize that the total area of these boxes all right and now suddenly this is a well-defined problem question

33:26 I'm not sure what will be the space complexity so that's it can take more space is okay the question was if bottom-up merge sort needs more space I I would say not much um you need a little bit of space for the queue so you need you need end pointers or or something like that you also have the buffer area of roughly size n so you could argue it needs more space than top down also top down is not entirely for free you need the recursion stack but that's logarithmic as opposed to linear so I give you that one uh bottom up has extra extra cost for this for the queue

34:11 now I wonder if you can somehow be smart and avoid having the queue in the first place it's much nicer to describe that way if you don't do the natural one you don't need the queue because the Run boundaries are regular you can just compute them on the Fly with existing runs I don't see how to do it right away but you know people can be smart but it's a fair point bottom up has this slight blemish of needings the the queue

34:45 okay so in this case the second looks like a well-defined optimization problem the only trouble is we want to spend very very little time on solving it otherwise again quick sort hey I'm done you're still finding out your merge order uh good luck with that all right we can reformulate the problem a little bit instead of saying this is all these black boxes we can say that's the the total length of the path from the root to all the entries in the array that happens to be the same thing and why is that the case so we would take each of these numbers and sum up how many steps we have to go down from the root it's the same because if you look up from from any one element it occurred in two boxes before so it contributed a factor of two to the cost before and now it contributes one two because that's its depth in the in the tree so it's not it's not uh any anything really intelligent it's uh it's just a different way of of writing the cost instead of saying we sum up at the node level we sum up at the element level

35:58 and so you can write this by saying okay I don't really care that these are different elements in the array I can just say this Leaf has weight six because there's six elements its depth is counted six times so you can write it as a fancy sum if you want you sum over all leaves and what do you sum the weight of the leaf times its depth all right uh now this is the point where you want to study algorithms and sometimes esoteric topics from the 70s turn out to be useful uh it turns out people have studied this problem it's exactly the same as asking for the best binary search tree so the model there is you have you have leaves so the null pointers the unsuccessful searches in the tree have weights there's some probability that you need to find uh okay how would that make sense uh suppose you store a set of numbers and you want to find out for a new number between what two numbers does it lie of the numbers that are stored uh why well because I I want you to do that I don't have a great application at this point maybe I should think of one that's more intuitive so you have a set of

37:18 numbers and for any new number you want to find with the fewest number of comparisons between which of the two numbers does it lie and you have some assumption that certain questions are more likely than others certain of the gaps have a higher probability of being asked than others finding the best binary search tree over those numbers to solve this this question is exactly the same as our question of minimizing this cost this is uh maybe not obvious but if you spell it if you write it down you get just exactly the same term that you try to minimize so what I'm what I'm getting at here is just this is a problem that people have studied and they have solutions for it so you can you can use those uh and um try to use them to find past a good merging order and that's what I did with my postdoc supervisor four years ago and so we found two two cool new methods that are much faster than and have nice properties compared to this top down and bottom up uh attempts that we've seen

38:08 Nearly-Optimal Mergesort

38:38 um okay let me show you the first one because that one is I think a little more intuitive it's called Peak sword because it peaks in the middle of the array uh we liked top down merge sorting principle the only problem was it was blind to the Run boundaries so instead of doing that you jump to the middle of your array and find the run that contains this position you can do that by just scanning to the right and continue on um as long as these are increasing continue to the left as long as this is decreasing so you find some sorted portion and this may be of any size you don't know right but it has some boundaries and now that the idea is just take the closer boundary and make that the cut of the topmost recursive call so you cut at this point because that's closer to the middle and well okay you cut and that becomes um that becomes the left and right of merge swords recursive calls and the rest is unchanged you don't even need this recurse this sordidness check anymore because you'll you'll make sure that you don't recurse on a sorted list by the same peaking step anyways if if the middle is contained in a run that is the entire

40:07 thing you're done so let's see this on this example how it continues so you peek in the middle of this recursive call again you would cut at the closer boundary same on on the right

40:29 if you continue doing this you get that kind of tree is it clear how the process will work so what I'm what I'm drawing with these red boxes is the runs right there's the numbers are omitted but it's really an array and you would have to find the sorted segments but the code for that is the same as for bottom-up merge sort okay so it sounds like um sounds like a fairly simple way to do

40:56 um if you want to implement this you can you can try to be a little smart and avoid finding a run twice it could sometimes happen in in weird cases that you would scan the same run twice and so we can avoid that by remembering what's the leftmost and rightmost run so how could this happen if you if you find this long run and you do this recursive call this this is the run that we've discovered at the topmost call in this recursive call we would jump to the middle and we would find we would ReDiscover this very same run that's kind of wasted effort we could have remembered that there was a run and so that's exactly what what I'm supposed proposing here you just remember uh if you have seen a run at the out end points and it turns out that this is enough so you remember what's the leftmost run the rightmost Run of any portion and that's all you'll ever need and they could both be empty

42:03 okay I think it's it's a getting late and you look a little confused so I think this is um that's the full code for this but I don't want to go into detail I just want to convince you that it fits on the slide it's not it's not too hard to spell it out in details so that you can just program it down um but the the intuition is the the bit I want you to take from it

42:06 Peeksort - Code

42:29 uh yeah I think no no much more comments on the code so the the only nasty bit is if you have these two points you have and a run you already know about in the Left End and on the Right End both of which could be in not there because you haven't seen anything there that gives you a bunch of different cases and so these uh these two if else statements here they handle all those cases that's the only complication

43:04 what I haven't shown you is uh how well does this work uh from what I've shown you so far is just oh just jump in the middle and cut sounds intuitively reasonable I haven't motivated much more than that um whether that's good so let's look at this this more tricky input from before that bottom-up merge sort really blue and top down merge sorted a little better uh if you if you do this with Peak swords so how would it go right you this is the middle so you would find this run so you would cut off this really big run uh as you suggested before and then on the right hand side it's a little more even split because the runs are of similar lengths so this natural or organically or automatically finds such kind of uh intuitively sensible cut points and it's very close to this h-bound

44:04 uh you can prove that the merge crust is essentially this minimal h plus at most 2N from a little bit of of overhead that is sometimes half and that was basically just uh reading again what people invented in the 70s the same the same trick of peaking in the middle works for binary search trees because they're the same problem