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 ...

Continue reading ...