Merge Sort

    public static void sort(int[] array, int low, int high) {
        if (low >= high) return;
        int mid = (high - low) / 2 + low;
        sort(array, low, mid);
        sort(array, mid + 1, high);
        merge(array, low, mid, high);
    }

    public static void merge(int[] array, int low, int mid, int high) {
        int[] helpArray = new int[array.length];
        for (int i = low; i <= high; ++i) {
            helpArray[i] = array[i];
        }

        int left = low, right = mid + 1;
        for (int curr = low; curr <= high; ++curr) {
            if (right > high) {
                array[curr] = helpArray[left];
                left++;
            } else if (left > mid) {
                array[curr] = helpArray[right];
                right++;
            } else if (helpArray[left] > helpArray[right]) {
                array[curr] = helpArray[right];
                right++;
            } else {
                array[curr] = helpArray[left];
                left++;
            }
        }
    }