class MergeSort<E extends Comparable<E>> implements Sorter<E> {

	private E[] array, array2;

	public void sort(E[] array) {
		this.array = array;
		array2 = array.clone();
		sort(0, array.length - 1);
	}

	private void sort(int left, int right) {
		if (left >= right)
			return;

		int middle = (left + right) / 2;
		sort(left, middle);
		sort(middle + 1, right);

		int i = left;
		int a = left;
		int b = middle + 1;
		while (a <= middle || b <= right) {
			// If both a <= middle and b <= right
			// copy the smaller of array[a] or array[b] to array2[i]
			// Otherwise just copy the remaining elements to array2
			if (a <= middle && b <= right) {
				if (array[a].compareTo(array[b]) < 0) {
					array2[i] = array[a];
					a++;
				} else {
					array2[i] = array[b];
					b++;
				}
				i++;

			} else {
				if (a > middle) {
					System.arraycopy(array, b, array2, i, array.length - b - 1);
				} else {
					System.arraycopy(array, a, array2, i, middle - a + 1);
				}
				break;
			}
		}

		System.arraycopy(array2, left, array, left, right - left + 1);
	}