public void merge(int[] array, int p, int q, int r) {
		int n1 = q - p + 1;
		int n2 = r - q;

		int[] leftA = new int[n1];
		int[] rightA = new int[n2];

		for (int i = 0; i < n1; i++) {
			leftA[i] = array[p + i];
		}

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

		int i = 0;
		int j = 0;

		for (int k = p; k < r + 1; k++) {
			//copy array if one of side branch is drained
			if (j > n2 - 1) {
				array[k] = leftA[i];
				i++;
			} else if (i > n1 - 1) {
				array[k] = rightA[j];
				j++;
			} else if (leftA[i] <= rightA[j]) {
				array[k] = leftA[i];
				i++;
			} else if (leftA[i] > rightA[j]) {
				array[k] = rightA[j];
				j++;
			}
		}

	}