/*
 * Average and worst-case performance of O(n log n). 
 */

void mergesort(int[] array, int low, int high){
	if(low < high){
		int middle = (low + high) / 2;
		mergesort(array, low, middle); // Sort the left part
		mergesort(array, middle + 1, high); // Sort the right part
		merge(array, low, middle, high); // Merge
	}
}

void merge(int[] array, int low, int middle, int high){
	int[] helper = new int[array.length];
	/*
	 * Copy the array into helper
	*/
	for(int i = low; i