import java.util.concurrent.atomic.AtomicInteger;

public class ThreadedMerge extends Thread{
	
	public int[] list;
	int start, end;
	
	static final AtomicInteger num = new AtomicInteger(0);
	static int nrOfProcessors = Runtime.getRuntime().availableProcessors();
	
	public ThreadedMerge(int[] array, int pStart, int pEnd){
		list = array;
		start = pStart; end = pEnd;
	}
	
	public void run(){
		list = mergeSort(list, start, end);
	}
	
	/**
	 * 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[] sortedLeftPart = null;
		int[] sortedRightPart = null;
		
		int halfLength = length / 2;
		
		if(num.intValue() <= nrOfProcessors){
		
			num.set(num.intValue() + 1);
			ThreadedMerge tm1 = new ThreadedMerge(array, startIndex, startIndex + halfLength);
			//ThreadedMerge tm2 = new ThreadedMerge(array, startIndex + halfLength, endIndex);
			tm1.start();// tm2.start();
			sortedRightPart = mergeSort(array, startIndex + halfLength, endIndex);
			try{
				tm1.join();// tm2.join();
				//num.set(num.intValue() - 1);
				sortedLeftPart = tm1.list;
				
				
			}catch(InterruptedException e){
			
			}
		
		}else{
		
			sortedLeftPart = mergeSort(array, startIndex, startIndex + halfLength);
			sortedRightPart = mergeSort(array, startIndex + halfLength, endIndex);
			
		}
		return merge(sortedLeftPart, sortedRightPart);		
	}
	
}