import java.util.Random;
import java.util.Scanner;

/**
 * Class that uses concurrency to merge sort a list.
 *   @author Dave Reed
 *   @version 4/12/17
 */
 public class MergeSort {
	/**
	 * Top-level method for sorting an array of numbers using concurrency.
	 * @param a the numbers to be sorted
	 * @param threadCount the number of threads that can be spawned
	 */
	public static void mergeSortConcurrently(int[] a, int threadCount) {
		MergeSort.mergeSortConcurrently(a, 0, a.length-1, threadCount);
	}
	
	/**
	 * Helper method that recursively sorts the numbers in a range.
	 * @param a the numbers to be sorted
	 * @param minIndex minimum index in the range
	 * @param maxIndex maximum index in the range
	 * @param threadCount the number of threads that can be spawned
	 */
	public static void mergeSortConcurrently(int[] a, int minIndex, int maxIndex, int threadCount) {
		if (minIndex < maxIndex) {		
			int mid = (minIndex+maxIndex)/2;
			if (threadCount > 1) {
				Thread leftThread = new SortThread(a, minIndex, mid, threadCount/2);
				Thread rightThread = new SortThread(a, mid+1, maxIndex, threadCount/2);
				leftThread.start();
				rightThread.start();
				
				try {
					leftThread.join();
					rightThread.join();
				} catch (InterruptedException ie) {}
			}
			else {
				MergeSort.mergeSortConcurrently(a, minIndex, mid, threadCount/2);
				MergeSort.mergeSortConcurrently(a,  mid+1, maxIndex, threadCount/2);
			}
			
			MergeSort.merge(a, minIndex, maxIndex);
		}
	}
	
	/**
	 * Helper method that merges the two halves of a range in an array.
	 * @param a the numbers to be merged
	 * @param minIndex minimum index in the range
	 * @param maxIndex maximum index in the range
	 */
	public static void merge(int[] a, int minIndex, int maxIndex) {
		int[] copy = new int[maxIndex-minIndex+1];
		for (int i = minIndex; i <= maxIndex; i++) {
			copy[i-minIndex] = a[i];
		}
		
		int middle = (copy.length+1)/2;
		int front1 = 0;
		int front2 = middle;
		for (int i = minIndex; i <= maxIndex; i++) {
			if (front2 >= copy.length ||
					(front1 < middle && copy[front1] <= copy[front2])) {
				a[i] = copy[front1];
				front1++;
			}
			else {
				a[i] = copy[front2];
				front2++;
			}
		}
	}

	/////////////////////////////////////////////////////////////////////////
	
	public static void main(String[] args) {	
		Random randy = new Random();
		int size = 1000;

		System.out.println("Enter the thread limit: ");
		Scanner input = new Scanner(System.in);
		int numThreads = input.nextInt();
		input.close();
		
		while (true) {
			int[] nums = new int[size];
			for (int j = 0; j < size; j++) {
				nums[j] = randy.nextInt();
			}

			long startTime1 = System.currentTimeMillis();
			MergeSort.mergeSortConcurrently(nums, numThreads);
			long endTime1 = System.currentTimeMillis();
			
			for (int k = 0; k < nums.length-1; k++) {
				if (nums[k] > nums[k+1]) {
				    throw new RuntimeException("Not sorted correctly");
				}
			}

			System.out.printf("%10d elements  =>  %6d ms \n", size, endTime1 - startTime1);
			size *= 2;  
		}
	}
}