1. import java.util.concurrent.atomic.AtomicInteger;
  2.  
  3. public class ThreadedMerge extends Thread{
  4.    
  5.     public int[] list;
  6.     int start, end;
  7.    
  8.     static final AtomicInteger num = new AtomicInteger(0);
  9.     static int nrOfProcessors = Runtime.getRuntime().availableProcessors();
  10.    
  11.     public ThreadedMerge(int[] array, int pStart, int pEnd){
  12.         list = array;
  13.         start = pStart; end = pEnd;
  14.     }
  15.    
  16.     public void run(){
  17.         list = mergeSort(list, start, end);
  18.     }
  19.    
  20.     /**
  21.      * Merges two sorted int array into one new sorted array.
  22.      * @param lhs
  23.      * @param rhs
  24.      * @return
  25.      */
  26.     private static int[] merge(int[] lhs, int[] rhs) {
  27.         int[] result = new int[lhs.length + rhs.length];
  28.        
  29.         int leftIndex = 0;
  30.         int rightIndex = 0;
  31.         while(leftIndex < lhs.length && rightIndex < rhs.length) {
  32.             if(lhs[leftIndex] <= rhs[rightIndex]) {
  33.                 result[leftIndex + rightIndex] = lhs[leftIndex];
  34.                 leftIndex++;
  35.             } else {
  36.                 result[leftIndex + rightIndex] = rhs[rightIndex];
  37.                 rightIndex++;
  38.             }
  39.         }
  40.        
  41.         while(leftIndex < lhs.length) {
  42.             result[leftIndex + rightIndex] = lhs[leftIndex];
  43.             leftIndex++;
  44.         }
  45.        
  46.         while(rightIndex < rhs.length) {
  47.             result[leftIndex + rightIndex] = rhs[rightIndex];
  48.             rightIndex++;
  49.         }
  50.        
  51.         return result;
  52.     }
  53.    
  54.     /**
  55.      * Sorts an array from index <code>startIndex</code> (inclusive) to <code>endIndex</code> (exclusive).
  56.      * @param array
  57.      * @param startIndex
  58.      * @param endIndex
  59.      * @return new array that is sorted
  60.      */
  61.     private static int[] mergeSort(int[] array, int startIndex, int endIndex) {
  62.         int length = endIndex - startIndex;
  63.         if(length == 0) {
  64.             return new int[]{};
  65.         }
  66.         if(length == 1) {
  67.             return new int[]{array[startIndex]};
  68.         }
  69.        
  70.        
  71.         int[] sortedLeftPart = null;
  72.         int[] sortedRightPart = null;
  73.        
  74.         int halfLength = length / 2;
  75.        
  76.         if(num.intValue() <= nrOfProcessors){
  77.        
  78.             num.set(num.intValue() + 1);
  79.             ThreadedMerge tm1 = new ThreadedMerge(array, startIndex, startIndex + halfLength);
  80.             //ThreadedMerge tm2 = new ThreadedMerge(array, startIndex + halfLength, endIndex);
  81.             tm1.start();// tm2.start();
  82.             sortedRightPart = mergeSort(array, startIndex + halfLength, endIndex);
  83.             try{
  84.                 tm1.join();// tm2.join();
  85.                 //num.set(num.intValue() - 1);
  86.                 sortedLeftPart = tm1.list;
  87.                
  88.                
  89.             }catch(InterruptedException e){
  90.            
  91.             }
  92.        
  93.         }else{
  94.        
  95.             sortedLeftPart = mergeSort(array, startIndex, startIndex + halfLength);
  96.             sortedRightPart = mergeSort(array, startIndex + halfLength, endIndex);
  97.            
  98.         }
  99.         return merge(sortedLeftPart, sortedRightPart);     
  100.     }
  101.    
  102. }