public class ThreadedMerge extends Thread{
	
	public int[] list;
	int start, end;
	
	static int num = 0;
	
	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]};
		}
		
		Runtime runtime = Runtime.getRuntime();

        int nrOfProcessors = runtime.availableProcessors();
		
		int[] sortedLeftPart = null;
		int[] sortedRightPart = null;
		
		int halfLength = length / 2;
		
		if(num <= nrOfProcessors){
			num += 2;
			ThreadedMerge tm1 = new ThreadedMerge(array, startIndex, startIndex + halfLength);
			ThreadedMerge tm2 = new ThreadedMerge(array, startIndex + halfLength, endIndex);
			tm1.start(); tm2.start();
			
			try{
				tm1.join(); tm2.join();
				sortedLeftPart = tm1.list;
				sortedRightPart = tm2.list;
			}catch(InterruptedException e){
			
			}
		
		}else{
		
			sortedLeftPart = mergeSort(array, startIndex, startIndex + halfLength);
			sortedRightPart = mergeSort(array, startIndex + halfLength, endIndex);
			
		}
		return merge(sortedLeftPart, sortedRightPart);		
	}
	
}