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.

到目前為止，我們已經開發(fā)了一種分而治之的方法來計算數(shù)組的求逆數(shù)，因此我們將把數(shù)組分為兩部分，遞歸地計算左側和右側的求逆數(shù)。

我們已經確定了最大的挑戰(zhàn)，那就是快速計算拆分反轉的次數(shù)。

拆分反轉意味著數(shù)組的左半部分中的索引較早，數(shù)組的右半部中的索引第二。

這些恰恰是我們的兩個遞歸調用都將遺漏的反轉。

問題的癥結在于，可能有多達二次分割版本，如果以某種方式，它們得到了我們想要的運行時間，我們需要在線性時間內進行。

所以這真的很不錯。

這個想法將使我們做到這一點。

這個想法是背負合并短。

我的意思是，實際上，我們將需要更多的遞歸調用，以使計算拆分遞歸次數(shù)的工作變得更加容易。

這類似于您進行歸納證明時。

有時，當使歸納假設更強時，這就是使您推論歸納證明的原因。

因此，我們將要求遞歸調用不僅計算過去的倒數(shù)。

而且還可以對數(shù)組進行排序。

嘿

為什么不？我們知道排序速度很快。

合并簡短將在N中完成。

登錄時間，這是我們要拍攝的運行時間。

那么為什么不把它扔進去呢？也許它將對我們的綜合步驟有所幫助。

正如我們將看到的那樣。

那么，這能給我們帶來什么呢？為什么我們需要更多的遞歸調用？好吧，正如我們將要看到的，在幾張幻燈片中，合并子例程似乎幾乎只是為了計算拆分反轉的數(shù)量而設計的。

正如您將合并兩個排序的子數(shù)組時所看到的那樣，您自然會發(fā)現(xiàn)所有拆分的倒置。

因此，讓我更加清楚地了解我們以前的高級算法現(xiàn)在將如何發(fā)展，以便遞歸調用也可以排序。

因此，這是我們之前提出的高級算法，在該算法中，我們僅在左側，右側遞歸計數(shù)反轉，然后我們執(zhí)行了一些當前未實現(xiàn)的子例程count split，該子例程負責計算分割反轉的次數(shù)。

因此，我們將按以下方式進行補充。

因此，我們現(xiàn)在不稱其為計數(shù)和計數(shù)。

這將成為我們算法的名稱，遞歸調用再次僅調用排序和計數(shù)，因此現(xiàn)在我們知道，每個調用不僅將計算子數(shù)組中的求反數(shù)，而且還返回[sound]排序后的版本，因此第一個我們要返回數(shù)組b，它是傳遞給它的數(shù)組的排序版本，我們將從第二個遞歸調用中返回數(shù)組C的分類版本，然后傳遞給它的數(shù)組的排序版本，現(xiàn)在現(xiàn)在，除了對拆分版本進行計數(shù)外，該計數(shù)還拆分為多個版本，它負責合并兩個排序的子數(shù)組B和C。

對[聽不清]將負責。

用于輸出數(shù)組D。

，它是原始輸入數(shù)組A的分類版本。

因此，我還應該重命名我們未實現(xiàn)的子例程，以反映它現(xiàn)在更加雄心勃勃的議程。

因此，我們將其稱為合并。

然后數(shù)入。

現(xiàn)在，我們不應被要求合并的蘇聯(lián)團隊合并而嚇到。

兩者分別對B和C進行了排序，因為我們已經看到我們現(xiàn)在如何在線性時間內做到這一點。

因此，問題只是piggy帶在這項工作上，我們還可以在額外的線性時間內計算分割反演的次數(shù)嗎？

我們會看到可以的，盡管那顯然并不明顯。

所以您在這一點上應該再次提出一個問題，為什么我們不這樣做，為什么我們只是讓自己做更多的工作。

再一次希望是，回報是某種方式，通過要求我們對[音頻不清晰]進行遞歸調用，[音頻不清晰]版本將變得更容易，從而為直覺為什么為什么合并自然揭示了拆分反轉的數(shù)量發(fā)展了一些直覺，讓我們回想一下最初來自合并排序的合并服務器團隊是，所以這是我們之前看過幾個視頻的偽代碼，我將數(shù)組的字母重命名為與當前符號一致。

我們給了兩個排序的子數(shù)組，它們是從遞歸調用中返回的。

我稱他們?yōu)锽和C。

它們的長度N都超過2，并且負責產生B和C的排序組合。

這就是長度為N的輸出數(shù)組D。

同樣，這個想法很簡單。

您只需要兩個排序的子數(shù)組B和C。

然后取輸出數(shù)組d。

這對于填充和使用索引k是合理的，您將從左到右遍歷輸出數(shù)組d。

這就是外部for循環(huán)的作用。

然后您將保持指針I(yè)和j。

對于排序的子數(shù)組，分別為B和C。

唯一的觀察結果是，無論您尚未復制到D的最小元素是什么，它要么是B，您尚未看到的B的最左元素，要么是您尚未看到的C的最左元素。還沒見

B和C，由于被分類，剩下的最小[聽不清]必須是B或C可用的下一個。

因此，您只需要按照明顯的方式進行操作，就可以比較下兩個要復制的候選者。

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

無論哪一個較小，都可以復制。

因此，if語句的第一部分適用于B包含較小的語句的情況。

第二部分。

L語句用于C包含較小的語句。

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

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

現(xiàn)在要了解到底這與數(shù)組的拆分反轉有什么關系，我希望您考慮一下具有以下屬性的輸入數(shù)組A，該屬性具有沒有拆分反轉的屬性。

任何。

因此，在此數(shù)組中，在此輸入數(shù)組A中的每個反轉都將是一個左反轉，因此兩個索引最多等于2上的N或一個右反轉，因此兩個索引都嚴格大于兩個上的N。

現(xiàn)在的問題是，給定這樣的數(shù)組A，一旦合并，什么是。

在該步驟中，對于沒有拆分反轉的輸入數(shù)組A，排序后的子數(shù)組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.