So far, we've developed a divide and conquer approach
to counting the number of inversions of an array,
so we're gonna split the array in two parts,
recursively count inversions on the left and on the right.
We've indentified the key challenge
as counting the number of split inversions quickly.
Where a split inversion means that
the earlier indexes in the left half of the array,
the second indexes in the right half of the array.
These are precisely inversions that are going to be missed
by both of our recursive calls. And the crux of the problem is that there
might be as many as quadratic split versions, if somehow, they get the run
time we want, we need to do it in a linear time. So here's the really nice. This idea
which is going to let us do that. The idea is to piggyback on Merge Short. 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 when making the inductive
hyphothesis stronger, that's what lets you push through the inductive proof. So we're
gonna ask our recursive calls to not only count inversions in the array of their
past. But also along the way, to sort the array. And hey. Why not? We know sorting
is fast. Merge short 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 will help us in the combined
step. And as we will see it will. So what does this buy us? Why should we demand
more of our recursive calls? Well, as we'll see, in a couple slides, the merge
subroutine almost seems 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 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
call sort as well. So here's the high level algorithm we proposed before where
we just recursively count inversions on the left side, on the right side, and then
we have some currently unimplemented sub routine count split in which is
responsible for counting the number of split inversions. So we're just gonna
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 the sub array but also return [sound] a sorted
version so out from the first one we're going to get array b back which is the
sorted version of the array that we passed it and we'll get assorted array C back
from the second recursive call the sorted version of array t hat we passed it and
now the count is split in versions now in addition to counting splitted versions
it's responsible for merging the two sorted sub arrays B and C. To [inaudible]
will be responsible. For outputting an array D., which is an assorted version of
the original input array A. And so I should also rename our unimplemented
subroutine to reflect it now more ambitious agenda. So we'll call this,
merge. And count split in. Now we shouldn't be intimidated by asking our
combining Soviet team to merge. The two sorted separate B and C because we've
already see we now how to do that in linear time. So the question is just
piggybacking on that work, 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 aren't we doing this
why are we just making ourselves do more work. And again the hope is that the
payoff is some how [inaudible] versions becomes easier by asking our recursive
calls to [inaudible] so to develop some intuition for why that's true why merging
naturally uncovers the number of split inversions let's recall the definition of
just the original merge server team from merge sort was so here's the same pseudo
code 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 sub arrays,
these come back from recursive calls. I'm calling them B and C. They both have
length N over two and responsible for producing the sorted combination of B and
C. So that's an output array D of length N. And again the idea is simple. You're
just take the two sorted sub arrays B and C. And then you take the output array d.
Which are reasonable for populating and using index k you're going to traverse the
output array d from left to right. That's what this outer for loop here does. And
your gonna maintain pointers I and j. To the sorted subarrays, 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 gotta be either the, the leftmost element
of B that you haven't seen yet, or the leftmost element of C that you haven't
seen yet. B and C, by virtue of being sorted, the minimum [inaudible] 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 one to copy over.
You look at B of I, you look at C of 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. The L 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 array, in this input array A is
gonna be either a left inversion, so both indices are at most N over two or a right
inversion, so both indices are strictly greater than N over two. Now the question
is, given such an array A, what's, once you're merging. At the step what do the
sorted sub arrays B and C look like for input array A 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 contrapositive. Suppose you
had even one element in the first half which was bigger than any element in the
second half. That pair of element alone would constitute a split inversion. Okay?
So if you have no split inversions, then everything on the left is smaller than
everything on the, 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 gonna do? All right, so 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. Well if everything in B is less than
everything in C, everything in B is gonna get copied over into the [inaudible] ray D
before C ever gets touched. Okay? So merge had 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 concatonates C. Okay there's no
interleaving between the two. So no split inversions means nothing get copied from C
until it absolutely has to, until B is exhausted. So this suggests that perhaps
copying elements over from the second subarray, 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 gonna see a general pattern about copies from the second element C, second
array C [inaudible] exposing split inversions in the original input array A.
So let's look at a more detailed example, to see what that pattern is. Let's return
to it, the example in the previous video. Which is an array with six elements
ordered one, three, five, two, four, six. 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. So [inaudible] sorting what's gonna be done [inaudible] get to zero
inversions for both our recursive calls. Remember, in this example, it turns out
all of the inversions are split inversions. So, now let's trace through
the merge sub-routine invoked on these two sorted sub-arrays, and try to spot a
connection with the number of split inversions in the original 6-element
array. So, we initialize indices I and j to point to the first element of each of
these sub-arrays. So, this left one is b, and this right one is c and the output is
d. Now, the first thing we do, is we copy the one over from b into the upward array.
So, one goes there, and we advance this index over to the three. And, here nothing
really interesting happened, there's no. Reason to count any split inversions, and
indeed, the number one is not involved in any split inversions, cuz one is 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 two 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 something
over from c, before we've exhausted copying d. So we're hoping this will
expose some split in versions. 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
three comma two and five comma two. 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, two is smaller than the
remaining elements in B, the three and the five. But also because B is the left
array. The indices and the three and five have to be less than the index of this
two, so these are inversions. Two is further to the right than 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 inversions that involve
the element two. So now, let's go back to the emerging subroutine, so what happens
next? Well, next, we make a copy from the first array, and we sort of realize that
nothing really interesting happens when we copy from the first array, at least with
respect to split inversions. Then we copy the four over, and yet again, we discover
a split inversion, the remaining one which is five comma four. Again, the reason is,
given that four was copied over before, what's left in B, it's gotta be smaller
than it, but by virtue of being in the rightmost array, it's also gotta have a
bigger index. So it's gotta be a split inversion. And now the rest of the merge
subroutine executes. Without any real incident. The 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 inversions. And you will recall, from the
earlier video that these were inversions in the original array, three:2, five:2,
and five:4. We discovered them all in 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, and this specific execution, but no matter what the input array is, no
matter how many split inversions 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 what the pattern that we saw in the example. What works on
the right array. In C, we had the elements two, four, and six. Remember, every split
inversion has to, by definition, involve one element from the first half, and one
element from the second half. So to count [inaudible] inversions, we can just group
them according to which element of the second array there, did they involve. So
out of the two, four, and six, the two is involved in the splitter conversions, 3-2,
and 5-2. The three and the five were exactly the elements remaining in B. Bit
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 D was
empty when we copied the six over into the output array D. So what's the general
argument? What's quite simple. Lets just zoom in and fixate on a particular
element, X that belongs to that first half of the array that's among the first half
of the elements and let's just examine which Y's so which elements of the second
array the second half of the original input array involve with split versions of
X. So there are two cases depending on whether X is copies to the output array D
before or after Y now if X is copied to the output before Y well then since the
[inaudible] in sorted order that means X has got to be shorter than Y so there's
not going to be any split in inversion. On the other hand, if y is copied to the
output d before x, then again because we populate d left to right in sort order,
that's gotta 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 this is
indeed 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 what? So, those are exactly the number of
elements remaining in b, when y gets copied over. So, that proves the general
claim. [sound] 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
sub-arrays, it's a simple matter to just translate this into code, and get a linear
time implementation of a sub-routine that both merges and counts the number of split
inversions. Which, then, in the overall recursive algorithm, will 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 gonna write out the pseudocode, I'm just going to write
out what you need to augment the merge pseudocode, discussed a few slides ago,
by, in order to count split inversions as you're doing the merging. And this will
follow immediately from the previous claim, which indicated how split
inversions relate to, the number of elements remaining on 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 pseudocode of the two sorted sub-arrays,
you just keep a running total of the number of split inversions that you've
encountered, all right? So you've got your sorted sub-array b, you've got your sorted
sub-array c. You're merging these into an output array D. And as you traverse
through D and K from one to N you just start the count at zero and you increment
it by something each time you do a copy over from either from 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 gonna look at split inversions when we copy over for 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 tell us how
to increment this running count. And it falls 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
you'll recall that the left inversions are counted by the first recursive call, the
right inversions are counted by the second recursive call. Every inversion is either
left or right or split, it's exactly one of those three types. So with our three
different subroutines, the two recursive ones and this one here we successfully
count up all of the inversions of the original input array. So that's the
correctness of the algorithm, what's the running time? What we're calling merge
sort, we begin by just analyzing the running time of merge and then we discuss
the running time of the entire merge sort [inaudible]. Let's do the same thing here
briefly. So what's the running time of the [inaudible] team for this merging and
simultaneously cutting into split versions. 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 [inaudible], a single edition to our
running count. So constant time for element D, or linear time overall. So I'm
being a little sloppy here, sloppy in a very conventional way. But it is a little
sloppy about writing O of N plus O of N is equal to O of N. Be careful when you make
statements like that, right? So if you added O of N to itself N times, it would
not be O of N. But if you add O of N to itself a constant number of times, it is
still O of N. So you might, as an exercise, want to write out, a formal
version of what this means. Basically, there's some constant C [inaudible]. The
merge step takes a C11 in steps. There's a constant C2 so that the rest of the work
is in those C2 times N steps. So when we add them we get, get [inaudible] most
quantity C1 plus C2 times N steps, which is still [inaudible] because C1 plus C2 is
a constant. Okay? So linear work for merge, linear work the running count,
that's linear work in the subroutine overall. And no by exactly the same
argument we used in merge sort because we have two recursive calls on half the size
and we do linear work outside of the cursive calls, the overall running time is
O of N log N. So we really just piggybacked on merge sort The constant
factor a little bit to do the counting along the way, but the running time
remains at the go of [inaudible].