//Inversion.cpp//Finding the number of inversions in an array using merge sort//Let A[1...n] be an array of n distinct numbers. If i<j and A[i]>A[j],//then teh pair (i,j) is called an inversion of A//This code doesn't work#include<iostream>#include<vector>#include<algorithm>#include<string>#define MAX_INT 100000int me;using namespace std;void Merge(int A[], int p, int q, int r){ int n1=q-p+1; int n2=r-q; int *L=new int[n1+1]; int *R=new int[n2+1]; for(int i=0;i<n1;i++) L[i]=A[p+i-1]; for(int j=0;j<n2;j++) R[j]=A[q+j]; L[n1]=MAX_INT; R[n2]=MAX_INT; int i=0; int j=0; for(int k=p-1;k<r;k++) { if(L[i]<=R[j]) { A[k]=L[i]; i=i+1; me++; } else { A[k]=R[j]; j=j+1; } }}////////////////////////////////////////////void MergeSort(int A[], int p, int r){ if(p<r) { int q=(p+r)/2; MergeSort(A,p,q); MergeSort(A,q+1,r); Merge(A,p,q,r); }}///////////////////////////////////////////////int main(){ int n; cin>>n; int *A=new int[n]; for(int i=0;i<n;i++) cin>>A[i]; MergeSort(A,1,n); for(int i=0;i<n;i++) cout<<A[i]<<"\t"; cout<<endl<<me; getchar(); getchar(); return 0;}