private static void merge(int[] a, int begin, int mid, int end) {
        int[] b = new int[mid - begin + 1];
        int[] c = new int[end - mid];
        int p = begin, q = mid + 1;
        for (int i = 0; i < b.length; i++) {
            b[i] = a[p++];
        }
        for (int i = 0; i < c.length; i++) {
            c[i] = a[q++];
        }

        p = 0;
        q = 0;
        int i = begin;
        while (p < b.length && q < c.length) {
            if (b[p] < c[q]) {
                a[i++] = b[p++];
            } else {
                a[i++] = c[q++];
            }
        }
        while (p < b.length) {
            a[i++] = b[p++];
        }
        while (q < c.length) {
            a[i++] = c[q++];
        }
    }