Mergesort.java

public void mergeSort(int[] array) {
	divide(array, 0, array.length / 2, array.length - 1);
}

public void divide(int[] array, int low, int middle, int high) {
	if(high >= middle && middle > low) {
		divide(array, low, middle/2, middle - 1);
		divide(array, middle, ((high - middle + 1) / 2) + middle, high);
		merge(array, low, middle, high);
	}
}

public void merge(int[] array, int low, int middle, int high) {
	int[] helper = new int[array.length];
	
	for(int i = 0; i < array.length; i++) {
		helper[i] = array[i];
	}
	
	int leftIndex = low;
	int rightIndex = middle;
	int count = low;
	
	while(leftIndex < middle && rightIndex <= high) {
		if(helper[leftIndex] <= helper[rightIndex]) {
			array[count++] = helper[leftIndex++];
		} else {
			array[count++] = helper[rightIndex++];
		}
	}
	
	while(leftIndex < middle) {
		array[count++] = helper[leftIndex++];
	}
}