(44). 20.4 COUNT INVERSION - anishsingh90/Data_Structure_And_Algorithm_In_Cpp_github.io GitHub Wiki

//COUNT INVERSION #include <bits/stdc++.h> using namespace std;

long long merge(int arr[],int l,int mid, int r){ long long inv = 0; int n1 = mid - l + 1; int n2 = r - mid; int a[n1]; int b[n2]; for(int i=0; i<n1; i++){ a[i] = arr[l+i]; } for(int i=0; i<n2; i++){ b[i] = arr[mid+i+1]; } int i=0 , j=0 , k=l; while(i<n1 and j<n2){ if(a[i] <= b[j]){ arr[k] = a[i]; k++; j++; } else{ arr[k] = b[j]; inv += n1 - i;

// a[i], a[i+1] , a[i+2].... > b[j] and i < j k++; j++; } } while(i<n1){ arr[k] = a[i]; k++; i++; } while(j<n2){ arr[k] = b[j]; k++; j++; } return inv; }

long long mergeSort(int arr[], int l, int r){ long long inv = 0; if(l < r){ int mid = (l+r)/2; inv += mergeSort(arr,l,mid); inv += mergeSort(arr,mid+1,r); inv += merge(arr,l,mid,r); } return inv; }

int main(){ int n; cout <<"Enter the size of array: "; cin >> n;

int arr[n];
for(int i=0; i<n; i++){
	cin >> arr[i];
}

cout <<"Total Inversion in array is: "<< mergeSort(arr,0,n-1);

return 0;

}

/* OUTPUT: Enter the size of array: 3 3 2 1 Total Inversion in array is: 3 */