SPOJ 9722. Insertion Sort Solution

Problem Statement

Problem Type : Inversion Counting Problem(Merge Sort)

Difficulty : Medium.

Idea To Solve This Problem

This is an Inversion Counting Problem. As input size is large, A O(nlogn) sorting algorithm will suffices in this case. I had used merge sort to solve this problem.

 Implementation

#include <stdio.h>  

#define sz 100005
#define inf 1000000000  
long a[sz+2],L[sz+2],R[sz+2];  
long long cnt;

void merge(long p,long q,long r){  
 long i,j,k,ind1,ind2;  

 for(i = p,ind1 = 1;i <= q;i++){  
  L[ind1++] = a[i];  
 }  
 L[ind1] = inf;  

 for(i = q+1,ind2 = 1;i <= r;i++){  
  R[ind2++] = a[i];  
 }  
 R[ind2] = inf;  

 i = j = 1;  

 for(k = p;k <= r;k++){  
  if(L[i] > R[j]){  
   cnt += ind1 - i;  
   a[k] = R[j];  
   j++;  
  }  
  else{  
   a[k] = L[i];  
   i++;  
  }  
 }  
}  

void mergeSort(long p,long r){  
 if(p < r){  
  long q = (p+r)/2;  
  mergeSort(p,q);  
  mergeSort(q+1,r);  
  merge(p,q,r);  
 }  
}  

int main(){  
 long i,n,t;

 scanf("%ld",&t);
 while( t-- ){ 
  scanf("%ld",&n);
  for(i = 1;i <= n; i++){  
   scanf("%ld",&a[i]);  
  }  
  cnt = 0;  
  mergeSort(1,n);  
  printf("%lld\n",cnt);  
 }  

 return 0;  
}