1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2013
Posts
14
Rep Power
0

#### Inversion in mergesort

Hello,
I am trying to implement the number of inversion in an array with entries {2,4,1,3,5}

On paper, this array will yield 3 inversions (2,1) (4,1) (4,3)

but with my code, it yields 5. where am I getting it wrong?

Code:
```int mergeSort(int arr[], int array_size)
{
int *temp = (int *)malloc(sizeof(int)*array_size);
return mergesort(arr, temp, 0, array_size - 1);
}

int mergesort(int arr[], int temp[], int left, int right)
{
int mid;
int  inv_count = 0;
if (right > left)
{

mid = (right + left)/2;
inv_count  = mergesort(arr, temp, left, mid);
inv_count += mergesort(arr, temp, mid+1, right);
inv_count += merge(arr, temp, left, mid+1, right);
}
return inv_count;

}

int merge(int arr[],  int temp[], int left, int mid, int right)
{
int i, j, k;
int inv_count = 0;

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++];
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;
}```
2. Your program works as you expect.
Code:
```#if 0
-*- mode: compilation; default-directory: "/tmp/" -*-
Compilation started at Tue Jul  2 19:34:39

a=./c && make -k \$a && \$a
cc -Wall -g c.c -o c
2  4  1  3  5
INVERSIONS: 3
1  2  3  4  5

Compilation finished at Tue Jul  2 19:34:39
#endif

#include<stdlib.h>
#include<stdio.h>

#define DIM(A) (sizeof((A))/sizeof(*(A)))

int merge(int arr[],  int temp[], int left, int mid, int right) {
int i, j, k;
int inv_count = 0;
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++];
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;
}

int mergesort(int arr[], int temp[], int left, int right) {
int mid;
int  inv_count = 0;
if (right > left) {
mid = (right + left)/2;
inv_count  = mergesort(arr, temp, left, mid);
inv_count += mergesort(arr, temp, mid+1, right);
inv_count += merge(arr, temp, left, mid+1, right);
}
return inv_count;
}

int mergeSort(int arr[], int array_size) {
int *temp = (int *)malloc(sizeof(int)*array_size);
return mergesort(arr, temp, 0, array_size - 1);
}

void display(int*a,int n) {
int i;
for (i = 0; i < n; ++i)
printf("%3d",a[i]);
putchar('\n');
}

int a[] = {2,4,1,3,5};

int main() {
display(a, DIM(a));
printf("INVERSIONS: %d\n",mergeSort(a,DIM(a)));
display(a, DIM(a));
return 0;
}```
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2013
Posts
14
Rep Power
0
How about if you test it over this set of .txt file? What is the number of inversion that you got? Here is a link to the .txt file: http://txtup.net/HaGYX. I got an overflow and I tried using long long on the inv_counter but that didn't solve the problem either..
4. The largest value in that file is 99973, well within the range of long or even of a 32-bit int.

I took your program completely as-is, compiled it and got no errors or warnings, and ran it against your own data file. this is what I got:
C:TEST\help_desk>gcc -Wall mergesort.c

C:TEST\help_desk>a
2 4 1 3 5
INVERSIONS: 3
1 2 3 4 5

C:TEST\help_desk>
Why are you the only one who is always having problems with the exact-same code and data that we can use without a problem?

What compiler and OS are you using? I just used MinGW gcc version 2.95.3-6 (mingw special) under WinXP Pro.