class Solution {
static int inversionCount(int arr[]) {
// Code Here
return merge(0, arr.length-1, arr);
}
public static int merge(int i , int j, int nums[]){
int count =0;
if(i<j){
int m = (i+j)/2;
count+=merge(i,m,nums);
count+=merge(m+1,j,nums);
count+=sort(i,m,j,nums);
}
return count;
}
public static int sort(int i , int k, int j, int arr[]){
int count =0;
int a[] =new int[k-i+1];
int b[] = new int[j-k];//j-(k+1) + 1
for(int p=0;p<a.length;p++){
a[p] = arr[p+i];
}
for(int q = 0;q<b.length;q++){
b[q] = arr[q+k+1];
}
int p = 0;
int q = 0;
int r = i;
while(p<a.length && q<b.length){
if(a[p]<=b[q]){
arr[r] = a[p];
p++;
}
else{
arr[r] = b[q];
count+=a.length-p;
q++;
}
r++;
}
while(p<a.length){
arr[r] = a[p];
r++;
p++;
}
while(q<b.length){
arr[r] = b[q];
r++;
q++;
}
return count;
}
}
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)