#include<stdio.h>
#define MAX 10000
int InvCompCnt=0;
int MergeCompCnt=0;
int insertionCompCnt=0;
int fileRead (int arr[], char *file)
{
	FILE * fp;
	int i=0, d=0,idx=0;
	fp=fopen(file,"r");
	if (fp!=NULL)
	{
		while (d!=-1)
		{
			d=fscanf (fp,"%d",&i);
			arr[idx++]=i;
		}
	}
	else
	{
		printf ("unable to open the file");
	}
	fclose(fp);
	return idx;
}
int merge (int a[], int lb, int mid, int ub)
{
	int c[MAX], i=lb,j=mid+1,k=lb,invCnt=0;
	
	while(i<=mid && j<= ub)
	{
		/*
		*increment the invCount here to count the inversions if a[i]>a[j] 
		*/
		InvCompCnt++;
		MergeCompCnt++;
		if(a[i]<=a[j])
			c[k++]=a[i++];
		else
		{
			invCnt++;
			c[k++]=a[j++];
		}
	}
	/*
	* If elements are left in the left half of the array, then it implies that those elements are greater than
	*those in the right half of the array and also appear earlier, i.e they are present in the first (left) half
	*/
	while(i<=mid)
	{
		invCnt++;
		InvCompCnt++;
		c[k++]=a[i++];
	}
	while(j<=ub)
		c[k++]=a[j++];
		  	  
	for(i=lb;i<k;i++)
	{
		a[i]=c[i];
	}
	return invCnt;
}

int InversionCount(int a[], int lb, int ub)
{
	int mid,x=0,y=0,z=0;
	if (lb<ub)
	{
		mid=(lb+ub)/2;
		x=InversionCount(a,lb,mid);
		y=InversionCount(a,mid+1,ub);
		z=merge(a, lb, mid, ub);
	}
	return (x+y+z);
}

void swap (int *a, int *b)
{
	*b=*a + *b;
	*a=*b - *a;
	*b=*b - *a;
}

void insertionSort (int *a, int n)
{
	int i, j, key;
	for (i=0; i<n; i++)
	{
		key=a[i];
		for (j=i+1; j<n; j++)
		{
			insertionCompCnt++;
			if (a[i]>a[j])
				swap (&(a[i]), &(a[j]));
		}
	}
}

int main()
{
	int MergeSortArr[MAX], n=0, invNum=0, InsertionSortArr[MAX];
	char *file="<Put the full file path>\\PiTo10000Digits.txt";
	n=fileRead(MergeSortArr, file);
	invNum=InversionCount(MergeSortArr,0,n-1);
	n=fileRead(InsertionSortArr, file);
	insertionSort (InsertionSortArr, n-1);
	printf ("Number of inversions=%d; \nNumber of comparisons for computing inversions=%d",invNum, InvCompCnt);
	printf ("\nNumber of comparisons for sorting the array using:\n\t1. Merge Sort: %d\n\t2.Insertion Sort:%d",MergeCompCnt,insertionCompCnt);
}