import java.util.Random;

public class Exercise2 {
	public static Random random = new Random(100);
	
	public static void main(String[] args) {
		int[] array = createRandomArray(10000000);
		
		long time = System.currentTimeMillis();
		
		int[] sortedArray = sort(array);
		
		if(sortedArray.length != array.length || !isSorted(sortedArray)) {
			System.err.println("Failed to sort given array! :-(");
			return;
		}		
		System.out.println("Success! Sorting took " + (System.currentTimeMillis() - time) + "ms.");		
	}

	/**
	 * Creates a randomly filled array of given length
	 * @param length
	 * @return
	 */
	private static int[] createRandomArray(int length) {
		int[] result = new int[length];
		for(int i = 0; i < length; i++) {
			result[i] = random.nextInt();
		}
		return result;
	}
	
	/**
	 * Checks whether a given int array is sorted in ascending order  
	 * @param array
	 * @return <code>true</code> if the given int array is sorted; <code>false</code> otherwise.
	 */
	private static boolean isSorted(int[] array) {
		for(int i = 1; i < array.length; i++) {
			if(array[i] < array[i-1]) {
				return false;
			}
		}
		return true;
	}
	
	/**
	 * Merges two sorted int array into one new sorted array.
	 * @param lhs
	 * @param rhs
	 * @return
	 */
	private static int[] merge(int[] lhs, int[] rhs) {
		int[] result = new int[lhs.length + rhs.length];
		
		int leftIndex = 0;
		int rightIndex = 0;
		while(leftIndex < lhs.length && rightIndex < rhs.length) {
			if(lhs[leftIndex] <= rhs[rightIndex]) {
				result[leftIndex + rightIndex] = lhs[leftIndex];
				leftIndex++;
			} else {
				result[leftIndex + rightIndex] = rhs[rightIndex];
				rightIndex++;
			}
		}
		
		while(leftIndex < lhs.length) {
			result[leftIndex + rightIndex] = lhs[leftIndex];
			leftIndex++;
		}
		
		while(rightIndex < rhs.length) {
			result[leftIndex + rightIndex] = rhs[rightIndex];
			rightIndex++;
		}
		
		return result;
	}
	
	/**
	 * Sorts an array from index <code>startIndex</code> (inclusive) to <code>endIndex</code> (exclusive).
	 * @param array
	 * @param startIndex
	 * @param endIndex
	 * @return new array that is sorted
	 */
	private static int[] mergeSort(int[] array, int startIndex, int endIndex) {
		int length = endIndex - startIndex;
		if(length == 0) {
			return new int[]{};
		}
		if(length == 1) {
			return new int[]{array[startIndex]};
		}
		
		int halfLength = length / 2;
		int[] sortedLeftPart = mergeSort(array, startIndex, startIndex + halfLength);
		int[] sortedRightPart = mergeSort(array, startIndex + halfLength, endIndex);
		
		return merge(sortedLeftPart, sortedRightPart);		
	}
	
	
	/**
	 * Sorts a given array (ascending order)
	 * @param array
	 * @return
	 */
	private static int[] sort(int[] array) {
		//TODO: use multiple threads to speed up the sorting
		
		return mergeSort(array, 0, array.length);
	}
	
	
}