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.