Algorithm for Counting Inversion

We're gonna start by extending the merge sort algorithm to solve a problem involving counting the number of inversions of an array. Before we tackle the specific problem of counting the number of inversions in an array, let me say a few words about the divide and conquer paradigm in general. So again, you've already seen the totally canonical example of divide and conquer, namely merge sort. So the following three conceptual steps will be familiar to you. The first step, no prizes for guessing is you divide. The problem. Into smaller sub-problems. Sometimes this division happens only in your mind. It's really more of a conceptual step than part of your code. Sometimes you really do copy over parts of the input into say new arrays to pass on to your recursive calls. The second step, again no prizes here, is you conquer the sub-problems just using recursion. So for example, in Merge Sort, you conceptually divide the array into two different pieces. And then you [inaudible] with the conquer or sort to the first half of the array. And you, you do the same thing with the second half of the array. Now of the array. And you, you do the same thing with the second half of the array. problem, and then solving the sub problems recursively. Usually, you have some extra cleanup work after the recursive calls, and to stitch together the solutions to the sub problems into one for the big problem, the problem that you actually care about. Recall, for example, in Merge Sort, after our recursive calls, the left half of the array was sorted, the right half of the array was sorted. But we still had to stitch those together. Merge into a sorted version of the entire array. So the [inaudible] step is to combine. The solutions to the subproblem into one problem. Generally the largest amount of ingenuity happens in the third step. How do you actually quickly combine solutions to subproblems into one to the original problem? Sometimes you also get some cleverness in the first step with division. Sometimes it's as simple as just spliting a ray in two. But there are cases where the division step also has some ingenuity. Now let's move on to the specific problem of counting inversions and see how to apply this divide and conquer paradygm. So let begin by defining the problem formally now. We're given as input an array A with a length N. And you can define the problem so that the array a contains any ole distinct numbers. But, let's just keep thing simple and assume that it contains the numbers one through n. The integers in that range in some order. That captures the essence of the problem. And the goal is to compute the number of inversions of this array so what's an inversion you may ask well an inversion is just a pair of array [inaudible] I and J with I smaller than J so that earlier array entry the I entry is bigger than the latter one the Jake one so one thing that should be evident is that if the array contains these numbers in sorted order if the array is simply one two three four all the way up to N then the number of inversions is zero. The converse you might also want to think through if the array has any other ordering of the numbers between one and N other than the assorted one, then it's going to have a non. Of zero number of inversions.