@SuppressWarnings("unchecked")
	private static <E extends Comparable<E>> void merge(E[] array, int leftStart, int leftEnd, int rightStart, int rightEnd) {
		int length = rightEnd - leftStart + 1;
		E[] mergedArray = (E[]) Array.newInstance(array[0].getClass(), length);
		int index = leftStart;
		
		for (int i = 0; i < length; i++) {
			if (leftStart <= leftEnd && (rightStart > rightEnd || array[leftStart].compareTo(array[rightStart]) <= 0)) // <= for stable sort
				mergedArray[i] = array[leftStart++];
			else
				mergedArray[i] = array[rightStart++];
		}
		
		// copy mergedArray back into original array
		for (int i = 0; i < length; i++)
			array[index++] = mergedArray[i];
	}