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

Sort.java

By: a guest on Jun 18th, 2012  |  syntax: Java  |  size: 4.45 KB  |  views: 30  |  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. package multithreadedmergesort;
  2.  
  3. /**
  4.  *
  5.  * @author Davidthefat
  6.  */
  7. public class Sort extends Thread
  8. {
  9.     //Declares the pointer to the array of strings to be sorted. Any changes here will affect the original array.
  10.     private static String[] nums;
  11.     //Declares a temporary array of strings that will have a copy of all the data instead of pointing to it.
  12.     private static String[] temp;
  13.     //This stores the length of the array being sorted. This makes if faster since it does not have to calculate the length everytime.
  14.     private static int num;
  15.  
  16.     //Constructor thar gets passed the array to be sorted.
  17.     public Sort(String[] m)
  18.     {
  19.         //nums gets initiated to point to the original array.
  20.         nums = m;
  21.         //num gets initiated to the length of the array.
  22.         num = nums.length;
  23.         //temp gets initiated to an array of the same size as the original.
  24.         temp = new String[num];
  25.         //This names the thread to "Sort" to differentiate from the main thread for debugging purposes.
  26.         this.setName("Sort " + num);
  27.     }
  28.     @Override
  29.     //This gets called when you call Start().
  30.     public void run()
  31.     {
  32.         /*This calls the Method that sorts from index 0 to the length of array minus one.
  33.          * The third number is the number that governs the number of threads to run.
  34.          */
  35.         mergesort(0, num - 1, 2);
  36.         //This nulls the temporary variables to be garbage collected.
  37.         temp = null;
  38.         nums = null;
  39.     }
  40.     /*This Method calls the whole sorting threads.
  41.      * l is the low number.
  42.      * h is the high number.
  43.      * i is the number that governs the number of threads to run.
  44.      * For i = 2, 6 threads run. 4 are running concurrently.
  45.      * i = 3, 14 thread run. 8 are running concurrently.
  46.      * Number of Threads running concurrently = 2^i.
  47.      */
  48.     public static void mergesort(int l, int h, int i)
  49.     {
  50.         //This checks if the high number is higher than low number.
  51.         if (l < h)
  52.         {
  53.             //The middle number is set at the half way mark between low and high numbers.
  54.             int m = (l + h) / 2;
  55.            
  56.             //If i is greater than 0, it runs different concurrent threads for each section of the array
  57.             //to be split and joins the thread into the mother thread.
  58.             //The i gets decremented here.
  59.             if(i > 0)
  60.             {
  61.                 merger t1 = new merger(l, m, i - 1);
  62.                 merger t2 = new merger(m + 1, h, i - 1);
  63.                 t1.start();
  64.                 t2.start();
  65.                 try
  66.                 {
  67.                     t1.join();
  68.                     t2.join();
  69.                 }
  70.                 catch(InterruptedException e)
  71.                 {
  72.                     System.out.println(e.getMessage());
  73.                 }
  74.             }
  75.             //If i == 0, it runs it in the current thread and not spawning new threads.
  76.             else
  77.             {
  78.                 mergesort(l, m, 0);
  79.                 mergesort(m + 1, h, 0);
  80.             }
  81.             System.arraycopy(nums, l, temp, l, h - l + 1);
  82.             //This merges while sorting each section of the array.
  83.             merge(l, m, h);
  84.         }
  85.     }
  86.     //This Method is where the magic happens. Traditional merge.
  87.     //Think l to m is first array and m + 1 to h is the seocond array.
  88.     private static void merge(int l, int m, int h)
  89.     {
  90.         int i = l;
  91.         int j = m + 1;
  92.         int k = l;
  93.         while(i <= m && j <= h)
  94.         {
  95.                 if (temp[i].compareTo(temp[j]) <= 0) //Checks if temp[i] is lexiconically less than or equal to temp[j].
  96.                 {
  97.                         nums[k] = temp[i];
  98.                         i++;
  99.                 }
  100.                 else
  101.                 {
  102.                         nums[k] = temp[j];
  103.                         j++;
  104.                 }
  105.                 k++;
  106.         }
  107.         while(i <= m) //This runs if
  108.         {
  109.                 nums[k] = temp[i];
  110.                 k++;
  111.                 i++;
  112.         }
  113.     }
  114. }
  115. //This runs the mergesort Method. This is meant to be its own thread.
  116. class merger extends Thread
  117. {
  118.     private int l;
  119.     private int h;
  120.     private int i;
  121.     public merger(int lo, int hi, int in)
  122.     {
  123.         l = lo;
  124.         h = hi;
  125.         i = in;
  126.         this.setName("merger " + in);
  127.     }
  128.     @Override
  129.     public void run()
  130.     {
  131.         Sort.mergesort(l, h, i);
  132.     }
  133. }
clone this paste RAW Paste Data