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);
    }

}