fork download
copy 
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int merge(int *a ,int s ,int mid, int e){
  5.   int i=s;
  6.   int temp[100000]={0};
  7.   int j=mid;
  8.   int count=0;
  9.   int k=s;
  10.   while(i<=(mid-1) && j<=e){
  11.      if(a[j]>=a[i])	temp[k++] = a[i++];
  12.      else{
  13.      	count+=(mid-i);
  14.      	temp[k++] = a[j++];
  15.      }
  16.   }
  17.  
  18.   while(i<=(mid-1))temp[k++]=a[i++];
  19.   while(j<=e)temp[k++]=a[j++];
  20.   for(int i=s;i<=e;i++)a[i]=temp[i];
  21.  
  22.  
  23.   cout<<"count when start is "<<s<<" end is "<< e<<" = "<<count<<" ";
  24.   return count;
  25. }
  26.  
  27. int ms(int *a , int s , int e){
  28.   int ans=0;
  29.   int right=0,left=0,cross=0;
  30.   if(e>s){
  31.   int mid = (s+e)/2;
  32.  
  33.   left =ms(a,s,mid);
  34.   left+= ms(a,mid+1,e);
  35.   left+= merge(a,s,mid+1,e);
  36.  
  37.   ans= left + right +  cross;
  38.   cout<<"left= "<<left<<endl;
  39.   }
  40.   return ans;
  41. }
  42.  
  43.  
  44. int main() {
  45.   int t;
  46.   cin>>t;
  47.   while(t--){
  48.     int n;
  49.     cin>>n;
  50.     int a[n];
  51.     for(int i=0;i<n;i++)  cin>>a[i];
  52.  
  53.     cout<<ms(a,0,n-1)<<endl;
  54.     for(int i=0;i<n;i++)	cout<<a[i]<<" ";
  55.   }
  56. 	return 0;
  57. }
Success #stdin #stdout 0s 4352KB
comments (?)
stdin
copy 
1
3
3 2 1
stdout
copy 
count when start is 0 end is 1 = 1 left= 1
count when start is 0 end is 2 = 2 left= 3
3
1 2 3
https://ideone.com/AzqqLr
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!