Code:

//header files added here..
unsigned long long sortAlgo(int arr[], int array_size);
unsigned long long mergesort(int arr[], int temp[], int left, int right);
unsigned long long merge(int arr[], int temp[], int left, int mid, int right);
#define MAX_VALUE 100000
int main()
{
FILE *fp;
char buff[255]; // You're not storing the whole file, just one line at a time
int buffInt[MAX_VALUE];
int i = 0;
int count;
fp = fopen("input.txt", "r");
if( fp == NULL )
perror("File failed to open");
else
{
while ( i <=100000 && fgets(buff, 255, fp) != NULL )
{
buffInt[i] = atoi(buff); //important line..
i++;
//printf("%s", buff);
}
fclose(fp);
count = i;
printf("%d\n", count);
printf("\n");
for (i=0; i<count; i++)
printf("%d:%d\n", i+1,buffInt[i]);
}
printf(" Number of inversions are %d \n", sortAlgo(buffInt, count));
return 0;
}
unsigned long long sortAlgo(int arr[], int array_size)
{
int *temp = (int *)malloc(sizeof(int)*array_size);
return mergesort(arr, temp, 0, array_size - 1);
}
unsigned long long mergesort(int arr[], int temp[], int left, int right)
{
int mid;
unsigned long long inv_count = 0ULL;
if (right > left)
{
/* Divide the array into two parts and call _mergeSortAndCountInv()
for each of the parts */
mid = (right + left)/2;
/* Inversion count will be sum of inversions in left-part, right-part
and number of inversions in merging */
inv_count = mergesort(arr, temp, left, mid);
inv_count += mergesort(arr, temp, mid+1, right);
/*Merge the two parts*/
inv_count += merge(arr, temp, left, mid+1, right);
}
return inv_count;
}
unsigned long long merge(int arr[], int temp[], int left, int mid, int right)
{
int i, j, k;
unsigned long long inv_count = 0ULL;
i = left; /* i is index for left subarray*/
j = mid; /* i is index for right subarray*/
k = left; /* i is index for resultant merged subarray*/
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
/*this is tricky -- see above explanation/diagram for merge()*/
//inv_count = inv_count + (mid - i);
inv_count = inv_count+ (mid - i);
}
}
/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];
/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];
/*Copy back the merged elements to original array*/
for (i=left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}

Tweet This+ 1 thisPost To Linkedin