dalex

// mergesort for you

static class Utils {

    private Utils() {}

    public static void mergeSort(int[] a) {
        mergeSort(a, 0, a.length - 1);
    }

    private static void mergeSort(int[] a, int leftIndex, int rightIndex) {
        final int MAGIC_VALUE = 50;
        if (leftIndex < rightIndex) {
            if (rightIndex - leftIndex <= MAGIC_VALUE) {
                insertionSort(a, leftIndex, rightIndex);
            } else {
                int middleIndex = (leftIndex + rightIndex) / 2;
                mergeSort(a, leftIndex, middleIndex);
                mergeSort(a, middleIndex + 1, rightIndex);
                merge(a, leftIndex, middleIndex, rightIndex);
            }
        }
    }

    private static void merge(int[] a, int leftIndex, int middleIndex, int rightIndex) {
        int length1 = middleIndex - leftIndex + 1;
        int length2 = rightIndex - middleIndex;
        int[] leftArray = new int[length1];
        int[] rightArray = new int[length2];
        System.arraycopy(a, leftIndex, leftArray, 0, length1);
        System.arraycopy(a, middleIndex + 1, rightArray, 0, length2);
        for (int k = leftIndex, i = 0, j = 0; k <= rightIndex; k++) {
            if (i == length1) {
                a[k] = rightArray[j++];
            } else if (j == length2) {
                a[k] = leftArray[i++];
            } else {
                a[k] = leftArray[i] <= rightArray[j] ? leftArray[i++] : rightArray[j++];
            }
        }
    }

    private static void insertionSort(int[] a, int leftIndex, int rightIndex) {
        for (int i = leftIndex + 1; i <= rightIndex; i++) {
            int current = a[i];
            int j = i - 1;
            while (j >= leftIndex && a[j] > current) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = current;
        }
    }

}