MergeSort.java

/**
 * Created by Ariel on 6/14/2016.
 */
public class MergeSort {


    public static void merge(int [] arr, int start, int mid, int end) {

        // our two buckets to compare later
        int low[]  = new int[(mid-start)+1];
        int high[] = new int[end-mid];

        int index = start;

        // Copy the first half to the low bucket
        for ( int i = 0; index <= mid; i++, index++ ) {
            low[i] = arr[index];
        }

        // Copy the second half to the high bucket
        for ( int j = 0; index <= end; j++, index++ ) {
            high[ j ] = arr[ index ];
        }

        // Compare low and high... and input the data into the original array in order
        int i = 0,
        j = 0;
        index = start;

        while ( i < low.length && j < high.length ) {

            if ( low[ i ] < high[ j ] ) {
                arr[ index ] = low[ i ];
                i++;
            }

            else  {
                arr[ index ] = high[ j ];
                j++;
            }

            index++;
        }

        // just copy the rest of the "empty bucket"

        while ( i < low.length ) {
            arr[ index ] = low[ i ];
            i++;
            index++;
        }

        while ( j <  high.length ) {
            arr[index] = high[j];
            j++;
            index++;
        }
    }

    public static void sort ( int [] arr, int start, int end ) {

        int mid = (int)Math.floor( ( start+end ) / 2);

        if ( end > start ) {

            sort( arr,start,mid );
            sort( arr,mid+1,end );

            merge( arr, start, mid, end );
        }
    }
}