# Description

Let A[1..n] be an array of n distinct numbers. If i < j and A[i]>A[j], then the pair (i,j) is called an inversion of A.

Give an algorithm that determines the number of inversions in any permutation on n elements in Θ(nlgn) worst-case time. (Hint: Modify merge sort.)

# Psuedocode

```M.Merge-Sort(A, p, r)
if(p < r)
q = (p + r) / 2;   // q is a type of int
left  = M.Merge-Sort(A, p, q)
right = M.Merge-Sort(A, q + 1, r)
inv   = M.Merge(A, p, q, r) + left + right
return inv
end if
return 0
end M.Merge-Sort```
```M.Merge(A, p, q, r)
n1 = q - p + 1   // length of left subarray
n2 = r - q       // length of right subarray

Let L[1..n1], R[1..n2] be a new array
for i = 1 to n1
L[i] = A[p + i - 1] // here i starts from 1. Whereas i starts from 0, L[i] = A[p + i]
end for
for i = 1 to n2
L[i] = A[q + i]     // here i starts from 1. Whereas i starts from 0, R[i] = A[q + i + 1]
end for

i = 1
j = 1
k = p
inv = 0
while i != n1+1 and j != n2+1 do // here i starts from 1. Whereas i starts from 0, i != n1 and j != n2
if L[i] <= R[j] then
A[k] = L[i]
i = i + 1
else
A[k] = R[j]
inv = inv + n1 - i + 1 // here i starts from 1. Whereas i starts from 0, inv = inv + n1 - i
j = j + 1
end if
k = k + 1
end while

if i == n1+1 then   // here i starts from 1. Whereas i starts from 0, i == n1
for m=j to n2 do
A[k] = R[m]
k = k + 1
end for
else if j == n2+1 then // here i starts from 1. Whereas i starts from 0, j == n2
for m=i to n1 do
A[k] = L[m]
k = k + 1
end for
end if

return inv
end M.Merge```

# Use Java to implement this algorithm

```public class Inverse {
public int inverse(int[] A){
return Merge_Sort(A, 0, A.length - 1);
}

private int Merge_Sort(int[] A, int p, int q){
int left = 0;
int right = 0;
int inv = 0;
if(p<q){
int mid = (p + q) / 2;
left = Merge_Sort(A, p, mid);
right = Merge_Sort(A, mid+1, q);
inv = Merge(A, p, mid, q) + left + right;
}
return inv;
}

private int Merge(int[] A, int p, int q, int r){
int n1 = q - p + 1;
int n2 = r - q;
int[] L = new int[n1];
int[] R = new int[n2];

for(int i=0; i<n1; i++){
L[i] = A[p+i];
}
for(int i=0; i<n2; i++){
R[i] = A[q+i+1];
}

int k = p;
int i = 0;
int j = 0;
int inv = 0;
while(i != n1 && j != n2){
if(L[i] <= R[j]){
A[k] = L[i];
i++;
}
else{
A[k] = R[j];
j++;
inv = inv + n1 - i; // key code
}
k++;
}

if(i == n1){
for(int l = j; l<n2; l++, k++){
A[k] = R[l];
}
}
else{
for(int l = i; l<n1; l++, k++){
A[k] = L[l];
}
}
return inv;
}
}```

# Test for this algorithm

`Inverse inv = new Inverse();Inverse inv = new Inverse(); `

`int[] A = {5,6,9,8,7,5,65,4,5,6,48,56,46,54,35,4}; `

`System.out.println(inv.inverse(A));`

`49`

# Illustration Note: The number in the circle of the figure is computed by `M.Merge(A, p, q, r)`.

### 2 thoughts on “Compute Inversions of an Array in Θ(nlgn)”

• 2017年9月20日 at 上午11:34
• 