So far we've developed a divide and conquer approach to count the number of inversions of an array. So we're going to split the array in two parts, recursively count inversions on the left, on the right. We've identified the key challenge is counting the number of split inversions quickly. Where a split inversion means that the earlier indexes on the left half of the array, the second index is on the right half of the array. These are precisely inversions that are going to be missed by both of our recursive calls. And the cracks or the problem is that there might be as many as quadratics but conversions. It somehow they go the run time they want. We need to do it in a linear time. So, here is the really nice idea which is going to let us do that. The idea is to piggy back on merge sort. By which I mean we're actually going to demand a bit more of our recursive calls to make the job of counting the number of split recursions easier. This is analogous to when you're doing a proof by induction, sometimes making the inductive hypothesis stronger, that's what lets you push through the inductive proof. So we're going to ask our recursive calls to not only count inversions in the array that they're passed, but also along the way to sort the array. And hey, why not? We know sorting is fast. Merge sort will do it in n log in time, which is the run time we're shooting for, so why not just throw that in? Maybe it'll help us in the combined step, and as we'll see, it will. So, what is this bias, why should we demand more recursive calls? Well, as we'll see in a couple of slides, the merge subroutine almost seem designed just to count the number of split inversions. As we'll see, as you merge two sorted sub arrays, you will naturally uncover, all of the split inversions. So, let me just be a little bit more clear about how our previous high level algorithm is going to now be souped up so that the recursive calls sort, as well. So, here is the high level algorithm we proposed before where we just recursively counted versions on the left side, on the right side. And then, we have some currently unimplemented subroutine counts splint if which is responsible for counting the number of split inversions. So we're just going to augment this as follows so instead of being called count now we're going to call it sort and count. That's going to be the name of our algorithm. The recursive calls, again, just invoke sort and count. And so now we know each of those will not only count the number of inversions in sub array, but also return a sorted version. So, out from the first one we're going to get arrayed B back which is the sorted version of the array that we past it and we got the sorted array C back from the second recursive call or sort of version of the array that we past it. And now, the counts split inversions now, in addition to count and split inversions is responsible for merging the two sort of subarrays, B and C. So CountSplitInv will be responsible for outputting an array D, which is a sorted version of the original input array A. And so I should also rename our unimplemented subroutine to reflect its now more ambitious agenda. So we'll call this mergeAndCountSplitInv. Now, we shouldn't be intimidated by asking our combining subroutine to merge the two sorted subarrays B and C, because we've already seen, we know how to do that in linear time. So the question is just, piggybacking on that worth, can we also count the number of split inversions in an additional linear time? We'll see that we can, although that's certainly not obvious. So you should again at this point have the question why are we doing this? Why are we just making ourselves do more work? And again the hope is that the payoff is somehow counting split inversions becomes easier by asking our recursive calls to give some additional work of sorting. So to develop some intuition for why that's true. Why merging naturally uncovers the number of splits inversions. Let's recall with just the definition of the original merge subroutine from merge sort was. So here's the same pseudocode we went through several videos ago. I have renamed the letters of the arrays to be consistent with the current notation. So we're given two sorted subarrays. These come back from a recursive calls. I'm calling them B and C. They both have length n/2 and were responsible for producing the sorted combination of B and C so that's an output array D of length n. And again the ideas simple, you just take the two sorted sub-arrays B and C and then you take the output array D which you're responsible for populating. And using an index k you're going to traverse the output D from left to right. That's what this outer form here does and you're going to maintain pointers i and j to the sorted sub arrays B and C respectively. And, the only observation is that whatever the minimum element that you haven't copied over to D yet is, it's got to be either the left most element of B that you haven't seen yet or the left most element of C that you haven't seen yet. B and C by virtue of being sorted, the minimum element remaining has to be the next one available to either B or C. So you just proceed in the obvious way. You compare the two candidates for the next ones that copy over. You look at B(i). You look at C(j). Whichever one is smaller, you copy over, so the first part of the if statement is for when B contains the smaller one. The second part of the else statement is for when C contains the smaller one, okay? So, that's how merge works. You go down B and C in parallel, populating D in sorted order from left to right. Now to get some feel for what on Earth any of this has to do with the split inversions of an array, I want you to think about an input array A that has the following property. That has the property that there are no split inversions whatsoever. So every inversion in this input array A is going to be either a left inversion, so both indices are at most n/2, or a right end version. So both indexes are strictly greater than n/2. Now, the question is, given such an array A, once you're merging at this step, what do the assorted subarrays B and C look like for an input array that has no split inversions? The correct answer is the second one. That if you have an array with no split inversions then everything in the first half is less than everything in the second half, why? Well, consider the contra-positive. Suppose you had even one element in the first half which was bigger than any element in the second half, that pair of elements alone would constitute a split inversion, okay? So if you have no split inversions then everything on the left is smaller than everything in the right half of the array. Now, more to the point, think about the execution of the merge subroutine on an array with this property, on an input array A where everything in the left half is less than everything in the right half. What is merge going to do? All right, just remember it's always looking for whichever is smaller the first element of remaining in B or the first element remaining in C and that's what it copies over. When everything in B is less than everything in C everything in B is going to get copied over in to the output array D before C ever gets touched. Okay, so merge has an unusually trivial execution on input arrays with no split inversions with zero split inversions First it just goes through B and copies it over then it just concatinate C. Okay, there's no interweaving between the two. So, no split in versions means nothing it copied from C, until it absolutely has to, until B is exhausted. So, this suggests that, perhaps, copying elements over from the second sub-array C has something to do with the number of split inversions in the original array, and that is in fact the case. So we're going to see a general pattern about copies from the second array C through the output array, exposing split inversions in the original input array A. So let's look at a more detailed example to see what that pattern is. So let's return to the example in the previous video, which is an array with six elements, ordered 1, 3, 5, 2, 4, 6. So we do our recursive call and in fact, the left half of the array is sorted and the right half of the array is already sorted. No sorting was going to be done and I'm actually going to get zero inversions for both our recursive calls. Remember in this example it turns out all of the inversions are split versions. So now let's trace through the merge sub routine invoked on these two sorted subarrays. And try to spot a connection with the number of split inversions in the original six element array. So we initialize indices i and j to point to the first element of each of these subarrays. So this left one is B and this right one is C and the output is D. And the first thing we do is we copy the 1 over from B into the top of array so 1 goes there and we advance this index over to the 3. And here, nothing really interesting happens, there's no reason to count on this split inversions and indeed the number one is not involved at any split inversions, because you want it smaller than all of the other elements and it's also in the first index. Things are much more interesting when we copy over the element 2 from the second array C. And notice, at this point, we have diverged from the trivial execution that we would see with an array with no split inversions. Now we're copying over something from C before we've exhausted copying B. So we are hoping this will expose some split inversions. So we copy over the two and we advance the second pointer j into C and the thing to notice is, this exposes two split inversions. The two split inversions that involve the element two. And those inversions are 3,2 and 5,2. So why did this happen? Well the reason we copied two over is because it's smaller than all the elements we haven't yet looked at in both B and C. So in particular 2 is smaller than the remaining elements in B, the 3 and the 5. But also because B is the left array, the indices of the 3 and the 5 have to be less than the index of this 2. So, these are inversions, 2 is further to the right in the original input array, and yet it's smaller than these remaining elements in B. So, there are two elements remaining in B, and those are the two split versions that involve the elements two. So, now let's go back to the merging subroutines, and what happens next. Well, next we'll make a copy from the first array and we sort of realize that nothing really interesting happens when we copy it from the first array, at least with respect to split in versions. Then we copy the four over, and yet again, we discover a split inversion, the remaining one, which is 5,4. Again, the reason is, given that 4 was copied over before what's left in B, it's got to be smaller than it, but by virtue of being in the rightmost array, it's also not going to have a bigger index, so it's gotta be a split inversion. Now the rest of the merge subroutines executes without any real incident. Five gets copied over and we know copies from the left array are boring and then we copy the six over and copies from the right array are generally interesting but not if the left array is empty. That doesn't involve any split versions. And you will recall from the earlier video that these were the inversions in your original array, 3252 and 54. We discovered them all on an automated method by just keeping an eye out when we copy from the right array C. So this is indeed a general principle so let me state the general claim. So, the claim is not just in this specific example, in this specific execution. But no matter what the inquiry is, no matter how many split inversion there might be, the split inversions that involve an element of the second half of the array are precisely those elements remaining in the first array when that element gets copied over to the output array. So this is exactly the pattern that we saw in the example. What were, so on the right array C, we have the elements two, four and six. Remember every split version has to, by definition, involve one element from the first half and one element from the second half. So the count for split inversions, we can just group them according to which element of the second array that they involve. So out of the two four and six, the two is involved in the split up inversions three two and five two. The three and the five were exactly the elements remaining in B when we copied over two. The split inversions involving four is exactly the inversion five, four and five is exactly the element that was remaining. In B when we copied over the four, there's no split inversions involving six and indeed, the element B was empty when we copied the six over in the output array D. So what's the general argument? Well it's quite simple. Let's just zoom in and fixate on a particular element x that belongs to that first half of that array. That's amongst the first half of the element. And let's just examine which y's, so which elements of the second array, the second half of the original input array, are involved in split inversions with x. So there are two cases, depending on whether x is copied over into the output array D before or after y. Now if x is copied to the output before y, well then since the output's in sorted order it means x has got to be less than y so there's not going to be any split inversion. On the other hand if y is copied to the output d before x then again because we populate the left to right in sorted order, that's got to mean that y is less than x. Now x is still hanging out in the left array so it has a less index than y, y comes from the right array so it's not a split inversion. So putting these two together, it says that the elements x of the array B that form split inversions with y are precisely those that are going to get copied to the output array after y. So those are exactly the number of elements remaining in B when y gets copied over. So that proves the general claim. So this slide was really the key insight. Now that we understand exactly why counting split inversions is easy, as we're merging together two sorted subarrays, it's a simple matter to just translate this into code and get a linear time of notation of a sub routine that both emerges and counts the number of split inversions. Which then in the overall course of the algorithm we'll have n log n running time just as in merge sort. So, let's just spend a quick minute filling in those details. So, I'm not going to write up the pseudo code. I'm just going to write what you need to augment the merge pseudo code discussed a few slides ago by in order to count split inversion as you're doing the merging. And this will follow immediately from the previous plan which indicated how split version relate to the number of elements remaining in the left array as you're doing the merge. So the idea is the natural one, as you're doing the merging, according to the previous pseudo code, of the two sorted subarrays you just keep a running total of the number of split inversions that you encounter. And so you've got your sorted subarray B, you've got your sorted subarray C. You're merging these into an output array D, and as you traverse through D and k goes from 1 to n, you just start out at zero and increment it by something each time you copy over from either B or C. So, what's the increment? Well, what did we just see, we saw the copies involving B don't count, we're not going to look at split inversions when to copy over from B, only when we look at them from C, right? Every split inversion involves exactly one element from each of B and C. So, I may as well count them via the elements in C and how many split inversions are involved with the given element of C, well it's exactly how many elements of B remain when it gets copied over. So, that tells us how to increment this running count. And, it follows immediately from the claim on the previous slide that this implementation of this running total counts precisely the number of split inversions that the original input array A possesses. And we'll call that the left inversions are counted by the first recursive call of the right inversions are counted by the second recursive call. Every inversion is either at left or right or splitt that's exactly one of those three types. So, with our three different subroutines, the two recursive ones and this one here, we successfully count of all the inversions of the original input array. So that's the correctness of the algorithm. What's the running time? We'll recall in mergesort, we began just by analyzing the running time of merge and then we discussed the running time of the entire mergesort algorithm. Let's do the same thing here briefly. So what's the running time of the subroutine for this merging and simultaneously counting the number of split inversions? Well there's the work that we do in the merging, and we already know that that's linear. And then the only additional work here is incrementing this running count, and that's constant time for each element of D, right? Each time we do a copy over we do some single addition to our running count. So constant time for element of D, or linear time over all. So, I'm being a little sloppy here. Sloppy in a very conventional way but it is a little sloppy by writing O(n) + O(n) = O(n). Be careful when you make statements like that. Right, so, if you added O(n) to itself n times, it would not be O(n), but if you add O(n) to itself a constant number of times, it is still O(n). So you might, as an exercise, want to write out a formal version of what this means. Basically there's some constant c1 so that the merge steps takes at most c1 n steps. There's a constant c2 so that the rest of the work is at most c2 times n steps. So when you add them, we get it's at most quantity c1 plus c2 times n steps, which is still big O(n), because c1 plus c2 Is a constant, okay? So, linear work for merge, linear work for the running count, so does linear work in the subroutine overall. And now, by exactly the same argument, we'll use in merge sort because we have two reversing calls in half the size. And with your linear work outside the recursive calls, the overall running time is O(n) log n. So, it really just piggybacked on merge sort upped to the constant factor a little bit to do the counting along the way, but the running time remains the big O(n log n).
