public static int[] merge(int[] A, int p, int q, int r) {
		int i = p, j = q + 1, k = 0;
		int[] tmp = new int[r - p + 1];

		while (i <= q && j <= r) {
			if (A[i] <= A[j]) {
				tmp[k] = A[i++];
			} else {
				tmp[k] = A[j++];
			}
			k++;
		}
		
		while (i <= q) {
			tmp[k++] = A[i++];
		}
		while (j <= r) {
			tmp[k++] = A[j++];
		}
		for (i = 0; i < k; i++) {
			A[p + i] = tmp[i];
		}
		return tmp;
	}