private static void merge(int[] a, int low, int mid, int high) {
		// low, ... mid, mid+1, ..., high
		int[] temp = Arrays.copyOf(a, a.length);
		int tempMid = mid;
		int index = low;

		while (low <= tempMid && mid + 1 <= high) {
			if (temp[low] <= temp[mid + 1]) {
				a[index++] = temp[low];
				low++;
			} else {
				a[index++] = temp[mid + 1];
				mid++;
			}
		}

		while (low <= tempMid) {
			a[index++] = temp[low];
			low++;
		}

		while (mid + 1 <= high) {
			a[index++] = temp[mid + 1];
			mid++;
		}
		// for (int i = 0; i < (high-low+1); i++) {
		// if (low <= tempMid && (mid + 1) <= high) {
		// if (temp[low] <= temp[mid + 1]) {
		// a[index] = temp[low];
		// low++;
		// } else {
		// a[index] = temp[mid + 1];
		// mid++;
		// }
		// } else if (low > tempMid && (mid + 1) <= high) { // left part is
		// empty
		// a[index] = temp[mid + 1];
		// mid++;
		// } else if (low <= tempMid && (mid + 1) > high){
		// a[index] = temp[low];
		// low++;
		// }
		// index++;
		// }
	}