Video 4-4: Mergesort with sorted check

0:02 In part two of the sorting unit, we'll look at some specific methods that exploit if the input has already some existing order and we can maybe uh speed up sorting even further. And these methods also turn out to work well in practice and so have the double benefit that I can show you some some cool novel results that also work uh in some of the standard libraries. Uh whereas the ideas are all very simple to uh explain and follow.

0:30 where we just came from. Um well, first of all, back to the comparisonbased model here. Everything is again in the world of generic comparison-based algorithms. No integer sorting here. Then our lower bound still applies. And um we've proven this lower bound for the worst case. In the worst case, I need log n factorial comparisons. The very same argument with a little bit of a closer look at these trees tells you the average case is is essentially the same because to have uh to have a tree with a certain number of leaves, most of the leaves are close to the lowest level. The optimal trees will always have leaves only on two adjacent levels. And so um maybe some inputs can be faster, but everything you pull up puts other things further down. You can only do this so much before the average blows up. So log of n factorial works out as a lower bound for the average as well. So if you have a completely random input or if you've shuffled it, you're definitely stuck with this log n factorial for the comparisons.

1:43 Merge sort and quicksort also kind of uh use that but even in the best case they cannot even profit from uh some very easy inputs. They always spend essentially their same cost. And you could ask yourself if this is if this is necessary or if you can somehow profit from extremely sorted things and is not just hypothetically a case that could happen. um you can you can invent examples or you can imagine um applications where this would happen. Say you have uh different processes that generate things in order and you combine them or you have some uh essentially sorted list that you add random things at the end or the data might have correlations from the start. So ideally we'd want to profit from that kind of presortordedness when it is there but not slow down the algorithms much if it's not there and that leaves very little room for um exploiting presortedness and we should essentially focus on cheap little things that we can do. That's my claim here. Uh one one simple thing we can always do I can start any sorting algorithm by first asking is the input already completely sorted and if if so then just stop.

3:09 Uh that of course um makes the best case linear no matter what the algorithm was and the best case is the sorted input but of course it doesn't help in most other cases at all and uh usually you waste these extra comparisons. This sounds like a rather stupid idea. Now, if you think about how quicksort and merge sort both work, they are recursive and are dividing conquer algorithms that visit essentially every subrange potentially. And so if we do this extra check not just um initially for the entire input but recursively for sub inputs it potentially is much more powerful and um the downside is that it usually adds too many comparisons. So we have to be a bit careful about it but it could in principle be enough. In particular, you can do this for quicksort and you gain a little bit. You gain something usually destroyed by the unstable partition. But there's a different algorithm where this is very easy to do and that is merge sort. If we were to check before the recursive call, we would have to check the entire n minus one comparisons for sortedness. Much more clever is this little trick. You first recurse on the left and right side, but then before you do the actual expensive step, the merging, you check if the input happens to be already sorted. And for merge sort, if you have these two sorted runs from the uh recursive calls, when is that already sorted? Well, only if this is sitting entirely on top of the other. And if that's the case, there's only these two elements that you have to compare. If the minimum of the second run is larger than the maximum of the left run, the entire thing is sorted. That's a single comparison and is very cheap to do. But if it's successful, it skips an entire linear time merge. Question.

5:44 >> I'm not sure. So, this is going from L to M. Um I'm always writing these um halfopen intervals because this is what virtually all programming languages do anyways. Uh you say the uh left index is inclusive and the right index is exclusive. I think the main the main reason why this is the quote correct way is that then you can just take the difference of the two as here right almost every divide and conquer algorithm starts with oh let n be the difference of the two pointers and then that's just the difference no plus minus one messiness I would actually say this is uh something you should train yourself to use it's just a convention but it's one that avoids mistakes takes most of the time and both Java and C++ and the major and and Python, they all use this convention. So you're um you're in good company.

6:53 Okay, so this is already not that bad. Um maybe at least it's a very cheap check. Uh what can you do? Uh for all of this section, um let's look at some slightly simplified cost metric. the merge cost which is the size of the outputs of all the merges. Uh this is roughly the number of comparisons you usually use. The best case for the merges is a bit fewer comparisons. Um but for a practical um comparison of algorithms, this is even maybe more true than comparisons that you pay for the movement of data. And then the size of the output is precisely what you generate as movement of data. So here's an example with um with 64 numbers and they are in sorted runs of 16 elements each. And if you brought some spine glass, maybe you can even see it. But this is roughly the structure. Or to be to be honest, it's rather more the last is the smallest and so on.

8:04 This is uh maybe like that. What would our merge sort algorithm with this sorted check do on this input? First of all, what would normal merge sort do? It would start at the top, cut in half, have a left recursive call and a right recursive call, and keep cutting in half until you're all the way down. And then on the way back up, it would produce merges. And these are precisely these gray boxes. And the total merge cost of standard merge sword, this one, is just summing up the total length of these gray boxes. And obviously here easy analysis this is n the width is always n times the number of levels you have which is login n again proves that merge sort uses n login comparisons or merge cost. But our sorted check here would eliminate almost all of these merges because all these everything inside of this range these all happen to be inside a run. So when I come back from say this one here, I'm looking at the two uh runs from the sub problems where just individual elements and with one comparison I find oh these are already in order. I don't have to move anything.

9:28 Then I'm looking at the the right child here and the same happens. And then I'm looking at the parent call and the same happens and so on and so forth. So here um I I get to a third of the cost with this single comparison. Now the comparison I have to do but it is uh overall um just one comparison per element. So here it helps a lot. So great seems to work. Now um how much can this help in principle and you know just as a um a handwavy version that you could make precise but for for the time being let's let's leave it with that. If we have a run of L elements that are already sorted, the best that I could could I that I could hope to gain from that is to not spend the comparisons I would have had to spend to sort these L elements. And so I should target essentially LO L as the savings from detecting this run of L elements.

10:32 And the same is true in merge cost. So you could say um what we save is what we would have paid to create this thing in the first place if we had to do that. And let's give this a name. If I have an input with with sorted runs of these lengths L1 up to LR, then um what I should what I should hope to pay is the cost for sorting the entire run, but then the entire input and then subtracting what I could save from each of these runs already being sorted. And you can of course um regroup this a little bit if you want. Um first of all this n is the same as summing up the li.

11:35 Then I have um the li I log li and okay let's then minus log n I'm essentially giving each of these let's write li i log n I'm splitting up this and I give each li the appropriate amounts of login then you can simplify this a bit further let me pull the minus is in and the li out.

12:06 And then you have log n minus log li. Then the logs combine to this. And this is why this is called h because now it has essentially the flavor of uh of an entropy function.

12:23 And the way I wrote it here is the unnormalized one where this uh where larger inputs get you a larger age. Let's leave it like that. That's the number of comparisons you would uh would hope to achieve with your methods. And indeed, you can you can prove that this is a lower bound. If you knew your input consists of these runs, you could think about the decision tree argument. the number of possible leaves is smaller now by precisely this. And you could work out that the height you still need is precisely h. Let's not do that here. It's um also not on the slides. Uh just kind of as a side note, if you apply the same method from before on almost the same input except that now the runs here are a bit shorter on the left and a bit longer on the right, then suddenly it doesn't work as well anymore. you only cut off these parts here and all the ranges here where there's um a run boundary contained inside these the merge result you have to do the merge and so here on this small example it looks like you get instead of this age what you would want to spend um a substantially larger cost.

13:49 Now, this is this is my motivation for saying maybe just blindly doing a recursive uh procedure that cuts things in half is not good enough anymore because we would want to recover somehow that these these red boundaries uh should be respected. But um if I'm at this topmost recursive call, I don't know yet where these red boundaries are. And so the best I can do is cut things in half. But that was precisely an unfortunate choice here. So instead, we'll now flip things around and try to work from detecting these runs back up.