public static void merge(int[] array, int p, int q, int r) {
		int n1 = q - p + 1;
		int n2 = r - q;
		int[] al = new int[n1 + 1];
		int[] ar = new int[n2 + 1];
		for (int i = 0; i < n1; i++) {
			al[i] = array[p + i];
		}

		for (int j = 0; j < n2; j++) {
			ar[j] = array[q + j + 1];
		}

		al[n1] = Integer.MAX_VALUE;
		ar[n2] = Integer.MAX_VALUE;
		int m = 0, n = 0;
		for (int k = p; k <= r; k++) {
			if (al[m] < ar[n]) {
				array[k] = al[m++];
			} else {
				array[k] = ar[n++];
			}
		}
	}