Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <limits.h>
- long int i,j,k,swap,q;
- long int L[50000],R[50000];
- long int merge(long int A,long int p,long int q,long int r)
- {
- long int n1,n2;
- n1=q-p+1;
- n2=r-q;
- for(i=0;i<n1;i++)
- L[i]=A[p+i];
- for(j=0;j<n2;j++)
- R[j]=A[q+j+1];
- L[n1]=INT_MAX;
- R[n2]=INT_MAX;
- i=0;
- j=0;
- swap=0;
- for(k=p;k<r;k++)
- {
- if(R[j]<L[i])
- swap=swap+n1-i;
- if(L[i]<R[j])
- {
- A[k]=L[i];
- i=i+1;
- }
- else
- {
- A[k]=R[j];
- j=j+1;
- }
- }
- return swap;
- }
- long int mergesort(long int A,long int p,long int r)
- {
- swap=0;
- if(p<r)
- {
- q=(p+r)/2;
- swap=swap+mergesort(A,p,q);
- swap=swap+mergesort(A,q+1,r);
- swap=swap+merge(A,p,q,r);
- return swap;
- }
- }
- int main()
- {
- unsigned int t;
- scanf("%ud",&t);
- long int n,arr[100000];
- while(t--)
- {
- scanf("%ld",&n);
- for(i=0;i<n;i++)
- {
- scanf("%ld",&arr[i]);
- }
- swap=mergesort(arr,0,n-1);
- printf("%ld",swap);
- printf("\n");
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment