You are viewing a single comment's thread. Return to all comments →
Use simple merge sort technique as it is O(nLogn) where as insertion sort is O(n^2)
#include<iostream> #include<cstdio> using namespace std; long long ans=0; void mergei(int arr[],int l,int r,int mid) { int ni=mid-l+1; int nj=r-mid; int L[ni],R[nj]; for(int i=0;i<ni;i++) L[i]=arr[i+l]; for(int j=0;j<nj;j++) R[j]=arr[j+mid+1]; int i=0,j=0,k=l; while(i<ni && j<nj) { if(L[i]<=R[j]) arr[k++]=L[i++]; else { arr[k++]=R[j++]; ans+=(ni-i); } } for(;i<ni;) arr[k++]=L[i++]; for(;j<nj;) arr[k++]=R[j++]; } void m_sort(int a[],int i,int j) { int mid=(i+j)/2; if(i<j) { m_sort(a,i,mid); m_sort(a,mid+1,j); mergei(a,i,j,mid); } } int main() { int t; scanf("%d",&t); while(t--) { int n; ans=0; scanf("%d",&n); int * a = new int[n]; for(int i=0;i<n;i++) scanf("%d",&a[i]); m_sort(a,0,n-1); cout<<ans<<endl; } return 0; }
Seems like cookies are disabled on this browser, please enable them to open this website
Insertion Sort Advanced Analysis
You are viewing a single comment's thread. Return to all comments →
Use simple merge sort technique as it is O(nLogn) where as insertion sort is O(n^2)