This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on May 8th, 2011  |  syntax: Java  |  size: 2.53 KB  |  views: 56  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. }
clone this paste RAW Paste Data