Algorithm for finding inversions in Merge Sort

Question

Please help in code reviews for readability, optimizing it, functionality etc.

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;

public class Merge {

    static BigInteger cntInv = new BigInteger("0");

    static void mergeSort(int[] array){

        if(array.length > 1){

            int[] left = leftArray(array);
            int[] right = rightArray(array);

            mergeSort(left);
            mergeSort(right);

            merge(array,left,right);
        }
    }

    static int[] leftArray(int[] array){

        int size = array.length/2;
        int[] left = new int[size];
        for(int i =0 ; i<size;i++){
            left[i] = array[i];
        }
        return left;
    }

    static int[] rightArray(int[] array){

        int mid = array.length/2;
        int size = array.length - mid ;
        int[] right = new int[size];

        for(int i = 0 ; i<size;i++){
            right[i] = array[i + mid];
        }
        return right;
    }

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

    int iLeft = 0;
    int iRight = 0;

    /** Traverse through the array */
    for(int i=0;i<array.length;i++){
        if(iRight >= right.length || (iLeft<left.length && left[iLeft]<= right[iRight]) ){

            array[i] = left[iLeft];
            iLeft++;

        }else{

            if(left.length > 0 && iLeft < left.length) {

                cntInv = cntInv.add(BigInteger.valueOf(left.length - iLeft));

            }

            array[i] = right[iRight];
            iRight++;   
        }      
    }

}

static void display(int[] array){

    for(int i=0; i<array.length; i++){

    //System.out.println("Index of " + i + " : " + array[i]);

    }

}

private static int[] buildIntArray(ArrayList<Integer> integers) {
    int[] ints = new int[integers.size()];
    int i = 0;
    for (Integer n : integers) {
        ints[i++] = n;
    }
    return ints;
}

public static void main(String args[]) throws NumberFormatException, IOException{

    ArrayList<Integer> arrayList = new ArrayList<Integer>();        
    BufferedReader reader = new BufferedReader(new FileReader("./num_list.txt"));
    String line = null;
    while ((line = reader.readLine()) != null) {
        arrayList.add(Integer.parseInt(line)); 
    }



    int[] array = buildIntArray(arrayList);   // new int[10];


    System.out.println("List of number in the array befor sort");

    display(array);

    mergeSort(array);

    System.out.println("List of number in the array after sort");

    display(array);     

    System.out.println("Done" + cntInv);


    }

}

Answer 1

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 > 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 < left.length || iRight < right.length){
        if(iLeft < left.length && (i_right >= right.length || left[iLeft] <= right[iRight]) {
            array[iOut++] = left[iLeft++];
        } else {
            array[iOut++] = right[iRight++];
        }
    }

}