Linear merge sort:

    private int[] mergeSort(int[] input, int fromIndex, int length) {
        if (length == 1)
            return new int[]{input[fromIndex]};
        int mid = length >>> 1;
        int[] sorted1 = mergeSort(input, fromIndex, mid);
        int[] sorted2 = mergeSort(input, (fromIndex + mid), (length - mid));
        return merge(sorted1, sorted2);
    }

    private int[] merge(int[] sorted1, int[] sorted2) {
        int[] merged = new int[sorted1.length + sorted2.length];
        int i = 0, j = 0, k = 0;
        while (i < sorted1.length && j < sorted2.length) {
            if (sorted1[i] < sorted2[j])
                merged[k++] = sorted1[i++];
            else
                merged[k++] = sorted2[j++];
        }
        if (i >= sorted1.length) {
            while (j < sorted2.length)
                merged[k++] = sorted2[j++];
        } else {
            while (i < sorted1.length)
                merged[k++] = sorted1[i++];
        }
        return merged;
    }

Fork and Join Merge Sort:

// Code to invoke fork and join merge sort
           MergeSorter mg = new MergeSorter(input, 0, input.length);
            ForkJoinPool pool = new ForkJoinPool();
            int[] output = pool.invoke(mg2);

    @Override
    protected int[] compute() {
        if (length == 1)
            return new int[]{input[startIndex]};
        int mid = length >>> 1;
        MergeSorter ms1 = new MergeSorter(input, startIndex, mid);
        ms1.fork();
        MergeSorter ms2 = new MergeSorter(input, (startIndex + mid), (length - mid));
        return merge(ms1.join(), ms2.invoke());
    }

    private int[] merge(int[] sorted1, int[] sorted2) {
        int[] merged = new int[sorted1.length + sorted2.length];
        int i = 0, j = 0, k = 0;
        while (i < sorted1.length && j < sorted2.length) {
            if (sorted1[i] < sorted2[j])
                merged[k++] = sorted1[i++];
            else
                merged[k++] = sorted2[j++];
        }
        if (i >= sorted1.length) {
            while (j < sorted2.length)
                merged[k++] = sorted2[j++];
        } else {
            while (i < sorted1.length)
                merged[k++] = sorted1[i++];
        }
        return merged;
    }

Will explain later ...