Merge Sort

    public static <T> void mergesort(T[] arr, Comparator<T> comparator) {
        T[] temp = mergeSorter(arr, comparator);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = temp[i];
        }
    }

    private static <T> T[] mergeSorter(T[] arr, Comparator<T> comparator) {
        if (arr.length > 1) {
                T[] array1 = (T[]) new Object[arr.length / 2];
                int array2Length = arr.length - arr.length / 2;
                T[] array2 = (T[]) new Object[array2Length];

                for (int i = 0; i < array1.length; i++) {
                    array1[i] = arr[i];
                }
                for (int j = 0; j < array2Length; j++) {
                    array2[j] = arr[j + arr.length / 2];
                }
                arr = merge(mergeSorter(array1, comparator), mergeSorter(array2, comparator), comparator);
        }
        return arr;

    }

    private static <T> T[] merge(T[] array1, T[] array2, Comparator<T> comparator) {
        T[] arr = (T[]) new Object[array1.length + array2.length];
        int arr1Size = array1.length;
        int arr2Size = array2.length;
        int arr1Index = 0;
        int arr2Index = 0;
        while (arr1Index + arr2Index < arr.length) {
            if ((arr2Index == arr2Size) || (arr1Index < arr1Size && (comparator.compare(array1[arr1Index], array2[arr2Index]) < 0))) {
                arr[arr1Index + arr2Index] = array1[arr1Index++];
            } else {
                arr[arr1Index + arr2Index] = array2[arr2Index++];
            }
        }
        return arr;
    }