MergeSort.java

public class MergeSort {
    private static int[] sorted;
  
    public static void mergeSort(int[] arr) {
        sorted = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int begin, int end) {
        if (begin < end) {
            final int middle = (begin + end) / 2;
            mergeSort(arr, begin, middle);
            mergeSort(arr, middle + 1, end);
            merge(arr, begin, middle, end);
        }
    }

    private static void merge(int[] arr, int begin, int middle, int end) {
        int i = begin;
        int j = middle + 1;
        int k = begin;

        while (i <= middle && j <= end) {
            if (arr[i] <= arr[j]) {
                sorted[k] = arr[i++];
            } else {
                sorted[k] = arr[j++];
            }

            k++;
        }

        int t;
        if (i > middle) {
            for (t = j; t <= end; t++, k++) {
                sorted[k] = arr[t];
            }
        } else {
            for (t = i; t <= middle; t++, k++) {
                sorted[k] = arr[t];
            }
        }

        for (t = begin; t <= end; t++) {
            arr[t] = sorted[t];
        }
    }
}