~~~ #include <iostream> using namespace std; int count = 0; void merge(int *a,int p,int q,int r){ int n1 = q-p+1; int n2 = r-q; int *m = new int[n1]; int *n = new int[n2]; for(int i=0;i<n1;i++) m[i] = a[p+i]; for(int j=0;j<n2;j++) n[j] = a[q+j+1]; int i=0,j=0,k=p; while(i<n1&&j<n2){ if(m[i]<=n[j]) a[k++] = m[i++]; else { int ni = q + 1 + j - k; count += ni; a[k++] = n[j++]; } } while(i<n1) a[k++] = m[i++]; while(j<n2) a[k++] = n[j++]; delete[] m,n; } 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 argc, char** argv) { int a[10] = {9,8,7,6,5,4,3,2,1,0}; mergeSort(a,0,9); for(int i=0;i<10;i++) cout<<a[i]; cout<<endl<<count<<endl; return 0; } ~~~