Counting Inversions (Issue with Large Input)

Question

I am currently working on counting inversions exercise using mergesort. The problem I am facing is when I have small or medium sized array the result is perfectly fine however if I use a very large testcase (an array of 100,000 integers) it does not give me correct number of inversions. I have no clue as to why is that happening. Here is my code:

static int [] helper;
static long count=0;
static Integer [] arr3;

private static void mergeSortMethod(Integer[] arr3) {
    int head=0;
    int tail=arr3.length-1;
    int mid=tail+((head-tail)/2);

    sort(arr3,head,tail);
}


private static void sort(Integer[] arr3, int low, int high) {

    if (high<=low){
        return;
    }
    int mid=low+ ((high-low)/2);

    sort(arr3,low,mid);
    sort(arr3,mid+1,high);

    merge3CountInvs(arr3,low,mid,high);

}

private static void merge3CountInvs(Integer[] arr3, int low, int mid, int high) {
    int i=low;
    int j=mid+1;
    int k=low;
    //to get size of first half of array
    int nArr1Elems=(mid-low)+1;

    for (int m=low;m<=high;m++){
        helper[m]=arr3[m];

    }

    while(i < mid+1 && j < high+1){// neither array empty
        if( helper[i] < helper[j] ){
            arr3[k++] = helper[i++];

        }

        else if ( helper[j] < helper[i] ){
            arr3[k++] = helper[j++];
            int numOFElements=nArr1Elems-i;
            count=count+(nArr1Elems-i);

        }
    }
    while(i < mid+1){ // arrayB is empty,
        arr3[k++] = helper[i++];
    }

    while(j < high+1){ // arrayA is empty,
        arr3[k++] = helper[j++];
    }

}

My solution gives correct answers when not using very large inputs however when I used test case of 100,000 integers that was the number of inversions I got:

From my implementation: -30588581433

Correct answer is: 2407905288

Any ideas? I would appreciate any sort of help. Thank you.

EDIT: As mentioned in the answers about the integer overflow case that is the point I am having a hard time to understand since variable "count" which causes overflow is initialized as "long" hence there should be no overflow in this case. I can not think of any other variable that would cause integer overflow in my code. Thanks a lot.

UPDATE:

There was no issue related to Integer overflow but thanks for the answers however Reddy's answer did point me into right direction so thanks once again. The only mistake in my algorithm was:

int nArr1Elems=(mid-low)+1; 

count=count+(nArr1Elems-i); 

When it should have been:

count=count+(mid-i+1); 

As we have to subtract from the elements left on the left side of array "after" sorting not initially when the subroutine is called since the index changes after sorting. I am writing my updated code in case if anyone else would end up in a similar issue as mine:

static int [] helper;
static long count=0;
static Integer [] arr3;

private static void mergeSortMethod(Integer[] arr3) {
    int head=0;
    int tail=arr3.length-1;
    int mid=tail+((head-tail)/2);

    sort(arr3,head,tail);
}


private static void sort(Integer[] arr3, int low, int high) {

    if (high<=low){
        return;
    }
    int mid=low+ ((high-low)/2);

    sort(arr3,low,mid);
    sort(arr3,mid+1,high);

    merge3CountInvs(arr3,low,mid,high);

}

private static void merge3CountInvs(Integer[] arr3, int low, int mid, int high) {
    int i=low;
    int j=mid+1;
    int k=low;

    for (int m=low;m<=high;m++){
        helper[m]=arr3[m];

    }

    while(i < mid+1 && j < high+1){// neither array empty
        if( helper[i] < helper[j] ){
            arr3[k++] = helper[i++];

        }

        else if ( helper[j] < helper[i] ){
            arr3[k++] = helper[j++];
         //to increment count with total number of elements left in arrayA after sorting
            count=count+(mid-i+1);

        }
    }
    while(i < mid+1){ // arrayB is empty,
        arr3[k++] = helper[i++];
    }

    while(j < high+1){ // arrayA is empty,
        arr3[k++] = helper[j++];
    }

}

Answer 1

You're trying to store a number greater than Integer.MAX_VALUE - try using a long instead

Answer 2

You are using numbers that do not fit into 32-bit integer and therefore you have an overflow. Use long for results smaller than 2^63 or java.math.BigInteger for all possible integers which fit in your memory.