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.

到目前为止，我们已经开发了一种分而治之的方法来计算数组的求逆数，因此我们将把数组分为两部分，递归地计算左侧和右侧的求逆数。

我们已经确定了最大的挑战，那就是快速计算拆分反转的次数。

拆分反转意味着数组的左半部分中的索引较早，数组的右半部中的索引第二。

这些恰恰是我们的两个递归调用都将遗漏的反转。

问题的症结在于，可能有多达二次分割版本，如果以某种方式，它们得到了我们想要的运行时间，我们需要在线性时间内进行。

所以这真的很不错。

这个想法将使我们做到这一点。

这个想法是背负合并短。

我的意思是，实际上，我们将需要更多的递归调用，以使计算拆分递归次数的工作变得更加容易。

这类似于您进行归纳证明时。

有时，当使归纳假设更强时，这就是使您推论归纳证明的原因。

因此，我们将要求递归调用不仅计算过去的倒数。

而且还可以对数组进行排序。

嘿

为什么不？我们知道排序速度很快。

合并简短将在N中完成。

登录时间，这是我们要拍摄的运行时间。

那么为什么不把它扔进去呢？也许它将对我们的综合步骤有所帮助。

正如我们将看到的那样。

那么，这能给我们带来什么呢？为什么我们需要更多的递归调用？好吧，正如我们将要看到的，在几张幻灯片中，合并子例程似乎几乎只是为了计算拆分反转的数量而设计的。

正如您将合并两个排序的子数组时所看到的那样，您自然会发现所有拆分的倒置。

因此，让我更加清楚地了解我们以前的高级算法现在将如何发展，以便递归调用也可以排序。

因此，这是我们之前提出的高级算法，在该算法中，我们仅在左侧，右侧递归计数反转，然后我们执行了一些当前未实现的子例程count split，该子例程负责计算分割反转的次数。

因此，我们将按以下方式进行补充。

因此，我们现在不称其为计数和计数。

这将成为我们算法的名称，递归调用再次仅调用排序和计数，因此现在我们知道，每个调用不仅将计算子数组中的求反数，而且还返回[sound]排序后的版本，因此第一个我们要返回数组b，它是传递给它的数组的排序版本，我们将从第二个递归调用中返回数组C的分类版本，然后传递给它的数组的排序版本，现在现在，除了对拆分版本进行计数外，该计数还拆分为多个版本，它负责合并两个排序的子数组B和C。

对[听不清]将负责。

用于输出数组D。

，它是原始输入数组A的分类版本。

因此，我还应该重命名我们未实现的子例程，以反映它现在更加雄心勃勃的议程。

因此，我们将其称为合并。

然后数入。

现在，我们不应被要求合并的苏联团队合并而吓到。

两者分别对B和C进行了排序，因为我们已经看到我们现在如何在线性时间内做到这一点。

因此，问题只是piggy带在这项工作上，我们还可以在额外的线性时间内计算分割反演的次数吗？

我们会看到可以的，尽管那显然并不明显。

所以您在这一点上应该再次提出一个问题，为什么我们不这样做，为什么我们只是让自己做更多的工作。

再一次希望是，回报是某种方式，通过要求我们对[音频不清晰]进行递归调用，[音频不清晰]版本将变得更容易，从而为直觉为什么为什么合并自然揭示了拆分反转的数量发展了一些直觉，让我们回想一下最初来自合并排序的合并服务器团队是，所以这是我们之前看过几个视频的伪代码，我将数组的字母重命名为与当前符号一致。

我们给了两个排序的子数组，它们是从递归调用中返回的。

我称他们为B和C。

它们的长度N都超过2，并且负责产生B和C的排序组合。

这就是长度为N的输出数组D。

同样，这个想法很简单。

您只需要两个排序的子数组B和C。

然后取输出数组d。

这对于填充和使用索引k是合理的，您将从左到右遍历输出数组d。

这就是外部for循环的作用。

然后您将保持指针I和j。

对于排序的子数组，分别为B和C。

唯一的观察结果是，无论您尚未复制到D的最小元素是什么，它要么是B，您尚未看到的B的最左元素，要么是您尚未看到的C的最左元素。还没见

B和C，由于被分类，剩下的最小[听不清]必须是B或C可用的下一个。

因此，您只需要按照明显的方式进行操作，就可以比较下两个要复制的候选者。

你看我的B，你看J的C。

无论哪一个较小，都可以复制。

因此，if语句的第一部分适用于B包含较小的语句的情况。

第二部分。

L语句用于C包含较小的语句。

好的，这就是合并的工作方式。

您从B到C并行排列，从左到右依次填充D。

现在要了解到底这与数组的拆分反转有什么关系，我希望您考虑一下具有以下属性的输入数组A，该属性具有没有拆分反转的属性。

任何。

因此，在此数组中，在此输入数组A中的每个反转都将是一个左反转，因此两个索引最多等于2上的N或一个右反转，因此两个索引都严格大于两个上的N。

现在的问题是，给定这样的数组A，一旦合并，什么是。

在该步骤中，对于没有拆分反转的输入数组A，排序后的子数组B和C的外观如何。

O(n log n) Algorithm for Counting Inversions II - Question 1

Suppose the input array A has no split inversions.

What is the relationship between the sorted subarrays B and C?

A. B has the smallest element of A, C the second-smallest, B the third-smallest, and so on.

B. All elements of B are less than all elements of C.

C. All elements of B are greater than all elements of C.

D. There is not enough information to answer this question.