Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

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