Algorithm for finding inversions in Merge Sort
For performance reasons, in Merge Sorts, it is common to have just one temporary array for the data, and then you use positions and lengths to work inside the relevant parts of the data.

The above is hard to describe without a code exammple, so the following will have to do.... a typical merge sort algorithm has a recursive method that looks something like:

public void mergeSort(int[] array, int[] temparray, int offset, int length) { ... }


Then, inside that system you do not need to keep creating internal arrays. The array-portion is merged in to the temparray, then copied back (or visa-versa - copied in to the temp array, then merged back).

Still, if you insist on creating mini-arrays for each merge set, you should at least consider using the native code in Java that does the bulk of the work.... for example, you could 'lose the right/left array methods, and your mergeSort could look like:

static void mergeSort(int[] array){

    if(array.length &gt; 1){

        int mid = array.length / 2;

        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length - mid);

        mergeSort(left);
        mergeSort(right);

        merge(array,left,right);
    }
}


As for the merge method, it is OK, but it is done as a 'pull' mechanism.... it pulls the values in to the final array by comparing the values from the source arrays. I find it easier to use a push mechanism.... Again, hard to describe without code:

static void merge(int[] array, int[] left, int[] right){

    int iLeft = 0;
    int iRight = 0;
    int iOut = 0;
    /** Traverse through the source arrays */
    while(iLeft &lt; left.length || iRight &lt; right.length){
        if(iLeft &lt; left.length &amp;&amp; (i_right &gt;= right.length || left[iLeft] &lt;= right[iRight]) {
            array[iOut++] = left[iLeft++];
        } else {
            array[iOut++] = right[iRight++];
        }
    }

}