#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);
}