Video 3-6: §3.5 Adaptive sorting

0:00 Intro

0:04 so in the second part on sorting i i want to look at how we can exploit pre-sortedness certain features of the input that might allow you to become better than otherwise this is in particular known as adaptive sorting in the sense that the algorithm adapts to the input at hand

0:23 Adaptive sorting

0:27 so a quick recap from the comparison based lower bound something i might have briefly mentioned but didn't stress at the time the lower bound how we showed it remember comparison tree you need n factorial leaves so the height had to be at least log of that the height of this comparison tree is the worst case number of comparisons that you need but you can extend this lower bound to an average case statement and it's it's essentially the same number because the best way to structure a tree like this if every outcome is equally likely is again to put all leaves as high as possible and then really the difference between height and an average depth of leaves is just one

1:15 so we also need these log of n factorial otherwise known asymptotically as n log n we also need that many comparisons in the average case so there's uh there's little hope if you're sticking to comparison base to to get much better than that but um maybe not everything is is as random in in practical application as this average case assumes it assumes every ordering is equally likely if you look from the other perspective both merge sort and quicksort essentially have a best case of n log n as well so their best case and their average case is very close and for merge sword best case and worst case is even very close it's generally a good thing just um because it means the worst case is usually quite good then but here for sorting we might be tempted to have a better best case and that's what this part is about so the question um i already asked initially can we somehow exploit that the input is almost sorted before we dive a bit into what this could formally mean what does almost sorted mean there's many ways how you could define that and we'll look at one one successful way to do that i wanted to list a few scenarios where you could potentially

2:41 believe that the input data is not randomly ordered one scenario is suppose you have some process that generates data and once in a while you have to sort that away and store it to disk so that you can efficiently search it so the goal is you have you have data that arrives over time but you also have to keep the history and you want to be able to search the history efficiently as a very standard scenario in one way or another let's look at the very simple version where the data is just ordered according to one criterion so it's it's sorted once you wrote it to disk once you wrote it to the archive but then the new data that arrives over the day is a small fraction of what you have in total so sorting the data continuously through the day would mean you sort this large archival data each time again so that seems seems a bit of a waste so instead you decide uh for the day for one day you just collect the data that arrives at the end of the day during the night you have some crown job that appends this to the sorted data and then sorts the entire list in this scenario there's always a large chunk that is

3:51 already sorted and some random things at the end appended you can have you can have this in different applications i think it's a fairly reasonable scenario another one is the data that arrives over time has some correlation in time so say it's it's a sensor that measures the temperature every minute it won't jump arbitrarily up and down it will slowly smoothly move up and down but if you do this over a year it's a lot of data and why would you want to sort it well you often instead of fully sorting it you want some summary data something like the median and then quartiles statistical summaries but it turns out that these are often quite conveniently done with sorting so that's another scenario you're sorting something where there is a correlation between the position and the value uh and the last one is a little slightly different

4:56 there's different sources of data that i want to collate at the end and each of the sources already sorts their piece of data just to make it more convenient and then sends that sorted junk to you and now you want to merge those all together now if you if you're a clever software engineer you notice that this is just merging and not sorting but sometimes people are lazy because libraries tend to have a sorting method but not a merging method so you might just put all the pieces that arrive back to back and sort the entire list so again that's something that might come up in big data frameworks fairly regularly they will probably try to make this smarter but one way is to just sort the entire list and again you have some some sortedness

5:45 and it would be somewhat cool if we had an algorithm that would just pick up the sortedness of these scenarios automatically so that what the lazy programmer did is actually a smart thing to do just give it to the sorting algorithm and let that one figure out that there is sortedness and how to exploit it makes sense so far so let's see what we could do and let's start with something very simple uh if we're just about improving the best case we could just before we start any sorting algorithm ask is the input already sorted how would you do this you compare the first two if they're in the right order you compare the next two and so on so you do n minus one comparison between all the adjacent pairs and if they all come out as less or equal you know the input is already sorted and you don't have to sort and if it's not sorted you sort right very simple so you can that shows that you can always get the best case to the best number of comparisons n minus one uh but of course it's a little uh limited right it only works for the exact sorted case and nothing of the previous scenarios so we definitely don't want to stop

6:06 Warmup: check for sorted inputs

6:55 there but now you might remember that both quicksort and merge sword and other sorting algorithms too are dividing conquer algorithms which means they recursively call themselves at least conceptually on sub-lists so say in the case of merge sword you sort the entire list by first sorting the left half recursively then sorting the right half recursively and then you merge the two sorted runs now instead of only doing this sortedness check at the topmost level and then if it's not completely sorted you throw up your hands and do sorting as if nothing had happened you can check for swordedness as sortedness in each recursive call so that would mean even if further down the line on a sub-list you encounter some sorted segment your sortedness check would pick that up and you can do this in in quicksort the same way so this has much more potential

7:59 but it has a it has the downside that in each recursive call you do a linear scan over the input to check if it's sorted and that brings us to the key dilemma of this of this section while this would in principle work okay it increases the constant factor for average case worst case for everything and it's quite likely it increases it by a factor two or something so would you be willing to slow down any input every input by a factor of two to sometimes gain a little bit and mostly the answer is no because sometimes things come pre-sorted but many times they don't and you don't want to sacrifice performance on one part for the other so adapting to the input is great but it's only useful if it has very minimal overhead okay

8:53 so that's how far we got with very simple tricks uh the rest of the of this of this unit we'll look at specifically merge sort because in merge sort we can improve on this trick um maybe you thought about this yourself sometime or you oh it's uh obvious to you maybe um but here is the trick and depending on what you prefer you can look at the text of the code uh let me conceptually say we do what we did here for the recursive call we avoid doing work if the input is already sorted but now for merge sort we don't check before we do the recursive calls we check after we've come back from the two recursive calls that means there's already the left half which is sorted and the right half which is sorted so if it happens to be that the left half is entirely below this the right half which i can find out by a single check then the input is sorted and i don't have to do the merge okay so the trick is to move the sortedness check after the recursive call which now means we can do it with a single comparison there's a slight downside that we do the recursive calls either way even though we may not have to do them

10:07 but it turns out this is not really a problem because they recursively apply the same strategy so if there was something to save the recursive calls return quickly so uh here in code this is all um this is what it looks like this is all the same as our merge sorter that we had last week with the exception of this the single line that i added here okay that's the type of algorithms we like for this for this section because they're very limited overhead it's a single additional comparison that can hardly do much damage the question is how good is this though and that's what we'll look at next

10:57 to have a clean way to measure and compare different merge sorts i want to again move away from counting comparisons because if you merge sometimes you can save a few comparisons it's usually not much and on average is almost nothing but it makes the discussion always a bit complicated so instead i want to look at this more abstract cost measure that's called merge cost and you can think about it again it's array reads and writes in a sense but here simplified to only the writes so the cost of one merge is the size of the output now the the real cost is maybe closer to twice that because you have to read the input read both runs and then write everything once that's what we discussed last time but let's let's avoid this factor of two on all the slides instead just say the merge cost of a merge is the length of its output which is roughly the number of comparisons and is proportional to cache misses etc so it's it's a very reasonable measure but it's a little uh a little more crude than comparisons itself let's look at a simple example um hope this is just um big enough for you to see so it's it's an input of 64 numbers and they come in in runs so this one is

12:25 already sorted and this next segment is already sorted and there's four of these runs okay um so that's that's the input we want to look at let's first see what standard merge sort does for this so what i wanted to stress on this slide we with our look from above we noticed that there are these runs of course what the algorithm sees is just this it doesn't know that there are already sorted segments we have to come up with a way for the algorithm to find out so what standard merge sort does is it doesn't find out it just keeps on merging it starts with pairs right so or or rather this is top down merge sort so we would start with the entire list recurs on the left and right half and keep going and on the way back we merge so what these pictures show you is the individual runs the individual elements and then sorted runs that are generated and there's one run that generates this another generates this and then where these two are recalled this one's merged so each of these is an intermediate stage of of the array and what's convenient about this picture is that the merge cost is just the the total length of all those gray bars

12:41 Mergesort with sorted check - Analysis

13:58 because each of the gray bars is the outcome of one merge and merge cost is the length of the output is the length of the result of the merge is that clear i mean you've probably seen a tree like this a recursive call tree for merge sort and this is just drawing the nodes not as a single little nodes but as wide as they as they would be if if you look at this the sub array that they work on okay

14:39 what i put down here at the bottom is the total merge cost for standard merge sort which in this case just double check is 64 for the final merge

14:56 it's 32 for these two but we have two of them so this comes out to 64 again and then we have 4 times 16 and so on and so forth so each level exactly sums up to 64. which you visually can see because they're all equally white

15:20 and we have six levels so six times 64 should be 384 okay good so that was standard merge sort uh what happens if we do this sortedness check in that case we can skip a lot of effort because whenever the entire entirety of this part here is contained within a sorted run we don't really have to do anything so when we come back from this one we would notice that this is already sorted and it is completely to the left of this one is is uh lower than the second heart so we skip the merge here as well and so here this works brilliantly we skip essentially everything up to the last two levels and that's why uh here we cut the merge cost to down to a third okay brilliant so problem solved it seems uh it works very well

16:25 uh let's briefly discuss how good it could possibly get because that's uh again we're now in the regime where we assume more about our input so the lower bound from before is not so meaningful instead

16:51 this had length l 16 in this case and what it's saved is exactly this this range which is 4 times 16. another way of saying it it is log of 16 times 16 because log 16 is the height of this subtree and 16 is the length

17:14 so that's what we saved in the previous example which is the cost that we would have had to spend to create this run from scratch if it wasn't already sorted with merge sort okay

17:30 so again if you wanted to create this one by sorting it instead of just being lucky you would have to spend exactly those 16 times four okay and that's in a sense the best we can hope for because what we get is a is a sorted segment merge sort would otherwise have to create that sorted segment and the cost for doing exactly that is the best we can hope for in saving

17:44 Alignment issues

18:03 there's another way to to prove this using the comparison trees similar to what we did for the generic bounds but that becomes a little more more nasty to write down so i left it out and leave it with this intuitive explanation

18:21 so we can um we can generalize this this thinking um to other inputs where the runs are not all the same length in general there's r runs so r sorted segments initially

18:42 and they have length l1 up to lr they can be different and they somehow sum to n okay the best we can hope for in terms of merge cost would be whatever merge sort needs for the entire thing minus the optimal saving so minus the cost we would have to spend to generate these runs but now we save it because they're already there okay

19:13 i should have added this here to this example if you if you see here then h is exactly 128 and exactly is exactly the cost that we spend in in top downward sort now in general this this simple method of checking if the runs are already sorted doesn't do so well here's a different example where the first runs the first two are slightly shorter these are length 15 and 15 and then 17 17 so the total length is the same but the runs are slightly less well aligned standard merge sort of course doesn't care it's sorting this from bottom up as before here's this lower bound h and what our our method so far does is is somewhere in the middle not as great as before and the reason is that we now have a run boundary inside each of these so these will not be completely sorted at the point where we come back from the recursive calls the sordidness check fails in these cases and you get this on all the levels at least for uh some of the outermost runs so it's not quite as great as we hoped for so maybe we can do something better instead

20:39 uh so here's code but um i i don't want you to really read this what i think i'll do is uh i'll explain this in a quick example how it works that's bottom up merge sort it's another another way of of doing merge sort that's that's well known it's just a different way of of writing it up and is very slightly different

21:04 let's do a tiny example with just um eight elements so what bottom up mergesor does is it maintains a queue of things that still has to merge so it maintains a queue of runs

21:22 and so initially it just goes through the input that's what this code does and it puts all the individual elements in the queue let's give these names so that we can identify them so initially the queue is

21:45 just filled with all these little runs and then in the second phase we always go through the entire queue and merge pairs of things into a bigger run and append the result again to the queue so the first round would produce these pairs from those

22:06 uh and after that the queue is containing these merged runs so i'll just write a b for the run that consists of a and b and it contains cd and ef and gh

22:21 and if you if you look at the code more carefully what it does is it takes the first two elements of the queue merges them and appends the result again to the end of the queue or well it uses a new queue so that you don't merge the last at first

22:39 if we do this one more round then again we pair those two up and those two then the tree looks like this then the queue contains the result of these

22:51 and a final round would merge the entire result and then we're done you see this essentially does the same thing as as top-down merge sort if the input is nice like in this case a power of two uh if it's not then sometimes you have some elements that are at the end lying around for longer than in top downwards so it's the bottom up is is slightly worse usually but only ever so slightly it's not very significant so that's another way to do merge sort instead of recursive you do it using these these cues you do passes over the input and you make the runs bigger each time okay

23:33 why do i talk about this i talk about this because there's a way to make this one pick up existing runs instead of here starting with single elements i might as well scan forward and see how long is this already sorted and put this on in the queue instead and that's what people call natural merge sword or natural bottom up merge sort this the second half of the code is exactly the same that's why i grade it out and the first is doing what i described so um you move forward so i is the start of the next run and then j moves forward um i get the slight feeling that there's a plus one missing uh so you move you start at position i you scan forward with j until the run ends and then this goes into the queue and then you jump to the right of that for the next round okay makes roughly sense the details again

24:42 the details of the code are not not so important for now uh so this this is promising uh but it also doesn't not doesn't always work perfectly um but uh let's let's first see a case where it works fine that's the one that we had before so this this top one was what the top down merge sort with the sortedness check did remember these were these red lines so all of these we needed to we needed to merge because they were including a run boundary bottom up merge sort would find these runs in this first phase and then just merge them up so that works perfectly in this case okay so we get almost the lower bound and do much better than the top down one as i already said

25:35 Natural Bottom-Up Mergesort - Analysis [2]

25:37 there is again a case where this doesn't work so well and that's if you have one very long run and then several short ones or other similarly imbalanced cases so you see here at bottom up merge sort picks up this long run and picks the other ones up as well but then it repeatedly merges this really long run into others making fairly little progress but writing this big run over and over again that doesn't look smart and indeed our merge sort top down with the sorted check does better here it doesn't do so well because it still uses here these these extraneous merges where we contain a run boundary but at least it doesn't completely mess up by merging this big run many many times

26:29 all right so it seems uh as far as we can get with these simple methods um this is about it we can either work bottom up or top down but both seems to work only for a subset of the cases reasonably well and the question is can we somehow do better

26:52 Good merge orders

26:55 at this point it might make sense to just take a step back we've run with the first idea that sounded reasonable and and looked how well it worked then i jumped to another idea that might be fairly natural with bottom-up merge sort if you know that one it's natural to start with existing runs but maybe this is as far as we get with these little changes let's just take a step back and think what is the underlying problem we're trying to to solve here

27:26 and i'd say conceptually there's there's two parts there's one that means we somehow want to identify existing runs and the the top down with sortedness check didn't really do that it kind of accidentally discovered some sorted ranges but it didn't really make an effort to pick up the exact boundaries and as we've seen this would have been a bit better but then there's the second part once we found the runs we want to merge them in a smart way in a smart order whereas the the bottom up one that just went through things in in phases and paired things up it didn't seem to work that well so this was kind of automatically achieved in top down merge sort because we recursively split things in half that tends to give balanced merges but it screwed up the other part the thing is the first is actually conceptually easy to find the runs we've done that in bottom-up merge sort so we should probably think about the second part again

28:29 so here's again this picture that i've i've drawn before there are the runs at the bottom and here's a particular way how to merge them and you can think of different orders but remember merge cost is just the total length of all those rectangles

28:51 which is the same as if i look at this as a binary tree and i walk from the root down to the leaves i can ask how long is this path and if you think about it each of these elements participates in a number of merges that is equal to the the height of the length of this path so the total merge cost is the same as following all of these paths as often as i have elements in this leaf so i would pay twice the cost of one two three because these two guys have both to take this path and i would pay i don't know six times the cost of these of two because these six elements of the last run they only have to walk down this path of length two so that's that's just rewriting uh the cost and in mathematical terms you could say uh we sum over all the leaves down there they have a weight which is just the length of the run and they have a depth that's the length of the path from the root now why is it helpful to write it that way maybe not immediately to you but it turns out that minimizing this over all possible ways to build a binary tree on top of

30:08 those leaves is a well-known problem and it's called the optimal binary search tree problem i'm not really going into this but this is historically what motivated what comes next so i want to point this out because this is this happens more often than in many contexts if you if you're stuck on a problem because you started working from existing algorithms with tweaking them a little bit sometimes you only get so far if you take a step back and formulate the problem a little more abstractly sometimes you can you discover a connection to some other problem and you can just look up what people have already found in terms of smart solutions for that problem so it's not always a question about inventing algorithms from scratch it's finding these connections and that's also why many parts in this module are throwing at you certain existing solutions for certain problems that you may or may not use in exactly that form but it helps you connect the dots if you encounter a new problem

31:16 Nearly-Optimal Mergesort

31:20 and in this case uh that's something that i did with uh in monroe together so we we saw attempts from people to improve merge sort and i knew well these binary these optimal binary search tree algorithms and then it was just a realization that the two problems are doing the same thing i don't want to talk extensively about optimal binary search trees even though it's a lovely topic i just want to present you the result it may look a little uh less less clear how to get there without that background but i think we'll have to live with that shortcut so uh well i guess almost four years ago now um we came up with with two algorithms uh peak sword and power sword you'll see something more about those soon um and they both essentially achieve what we try to do in the best possible way they have merge cost which is never more than age plus 2n and there's there's examples where you can't really do without that um and they're they're fast so they achieve to adapt to existing runs but they don't pay much on top of that and i want to briefly show you these because they're cool examples of slightly more sophisticated algorithms

32:46 for some parts of this i will tell you then that they're not part of the exam because they go a little too deep but it just fitted very nicely into the sorting unit as opposed to talking about this at the end of the lecture which i would otherwise have done but i thought it's better to move it here and then just point out don't worry about this part too much just look at it and enjoy it but you don't need to know it in detail

33:14 and i want to look at peak sort first because it's the much simpler method and then the other one will come in the second part after the break so peak sort is essentially like a top-down merge sword it's just with a twist so the problem in top down merge sort was we always cut things in half not looking at the input at all what happens in terms of sorted segments there so the idea in peak sort instead is to look into the middle but then find the run there so not just blindly chop there in half but look a little left and right of the middle and detect where the run ends and then cut there and recurse

34:02 so let's have a look at the concrete example so here's a list of runs now i abstract it from the array elements you should imagine that if you zoom in here further there would be some numbers and they would be sorted within each block but then they drop down between the blocks okay so we've already found the runs but this is conceptually the algorithm doesn't know the algorithm just sees the list so this segmentation into runs is only to help us see what happens so the first step is uh to jump into the middle of the array and from the middle to the left and to the left and to the right uh find a run that contains this middle point so the algorithm would find this run now but wouldn't see all the others it would only look at this middle run the run that straddles the middle point and then it would decide that the left end of this run is closer to the middle than the right end very clearly in this case and so you always want to cut at the boundary that is closer to the midpoint that's the the crucial step all right and once you've found this this topmost split well you cut there and that will be

35:20 so that this part merged with this part that would be the last merge you're going to do and now your recurs on left and right side as standard merge serve would have done just with a different cut point okay and then recursively do the same you find again you find this middle run you find the left is the boundary closer to the midpoint so you cut there that gives you another one and here again you find this run and find the closest cut point and if you keep doing you would end up with a merged tree like this so this is similar to the trees we've had before so you would merge these two first and these two first then the result with their neighbors and then finally the result of all these okay

36:15 i think up to this point i would expect you to to follow that rough idea um that part is is in addition and i wouldn't expect you to know that part so shall i mark this again

36:35 if you do exactly as i described you might end up detecting the same run several times because he recurs and the midpoint might lie into this in this run more than once in extreme cases and this is something we would like to avoid because if you have a very long run and you repeatedly scan that one that's that's wasted effort and it turns out you can avoid this by remembering runs and you only need to remember the two outermost so for each recursive call you have a run at the beginning and a run at the end that you remember and that is enough to avoid ever scanning any run twice um and i spelled this out in code but um this is just for you if you want to see the details i don't think i want to discuss it in in more detail than i what i said so there's there's an initial call and then um the algorithm follows the abstract steps i i laid out but it has to take into account that there's a sorted run on the left and and maybe on on the right as well and he wants to take into account that these already are known and you don't want to scan them again but the the key idea is

37:47 as i described okay let's let's very briefly just um on one example see how well this works so this was the the same example we had before with one fairly long run and then a bunch of smaller ones and here again the results you've seen a few slides back there's this lower bound that comes from you never save more than what would you would have paid to produce the runs this was the uh the bottom up one which didn't do well because it merged this first big run several times and the top down one was a bit better but also not not as great if you compare with this lower bound whereas peak sword is very close to the lower bound in this case and you see it merges the big run only once at the very end and it's trying to be somewhat smart with these runs here because the the last one is smaller than the others even though just a little bit so this ends up being merged a bit more often and some of the others a bit less often and that's exactly the kind of trade-offs that you need here so we can indeed have the best of both worlds um pixar gives you that the the best combination of these bottom

39:07 up top-down ideas by i would say doing a top-down with some insight or some look at the data before you decide where to cut