Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package multithreadedmergesort;
- /**
- *
- * @author Davidthefat
- */
- public class Sort extends Thread
- {
- //Declares the pointer to the array of strings to be sorted. Any changes here will affect the original array.
- private static String[] nums;
- //Declares a temporary array of strings that will have a copy of all the data instead of pointing to it.
- private static String[] temp;
- //This stores the length of the array being sorted. This makes if faster since it does not have to calculate the length everytime.
- private static int num;
- //Constructor thar gets passed the array to be sorted.
- public Sort(String[] m)
- {
- //nums gets initiated to point to the original array.
- nums = m;
- //num gets initiated to the length of the array.
- num = nums.length;
- //temp gets initiated to an array of the same size as the original.
- temp = new String[num];
- //This names the thread to "Sort" to differentiate from the main thread for debugging purposes.
- this.setName("Sort " + num);
- }
- @Override
- //This gets called when you call Start().
- public void run()
- {
- /*This calls the Method that sorts from index 0 to the length of array minus one.
- * The third number is the number that governs the number of threads to run.
- */
- mergesort(0, num - 1, 2);
- //This nulls the temporary variables to be garbage collected.
- temp = null;
- nums = null;
- }
- /*This Method calls the whole sorting threads.
- * l is the low number.
- * h is the high number.
- * i is the number that governs the number of threads to run.
- * For i = 2, 6 threads run. 4 are running concurrently.
- * i = 3, 14 thread run. 8 are running concurrently.
- * Number of Threads running concurrently = 2^i.
- */
- public static void mergesort(int l, int h, int i)
- {
- //This checks if the high number is higher than low number.
- if (l < h)
- {
- //The middle number is set at the half way mark between low and high numbers.
- int m = (l + h) / 2;
- //If i is greater than 0, it runs different concurrent threads for each section of the array
- //to be split and joins the thread into the mother thread.
- //The i gets decremented here.
- if(i > 0)
- {
- merger t1 = new merger(l, m, i - 1);
- merger t2 = new merger(m + 1, h, i - 1);
- t1.start();
- t2.start();
- try
- {
- t1.join();
- t2.join();
- }
- catch(InterruptedException e)
- {
- System.out.println(e.getMessage());
- }
- }
- //If i == 0, it runs it in the current thread and not spawning new threads.
- else
- {
- mergesort(l, m, 0);
- mergesort(m + 1, h, 0);
- }
- System.arraycopy(nums, l, temp, l, h - l + 1);
- //This merges while sorting each section of the array.
- merge(l, m, h);
- }
- }
- //This Method is where the magic happens. Traditional merge.
- //Think l to m is first array and m + 1 to h is the seocond array.
- private static void merge(int l, int m, int h)
- {
- int i = l;
- int j = m + 1;
- int k = l;
- while(i <= m && j <= h)
- {
- if (temp[i].compareTo(temp[j]) <= 0) //Checks if temp[i] is lexiconically less than or equal to temp[j].
- {
- nums[k] = temp[i];
- i++;
- }
- else
- {
- nums[k] = temp[j];
- j++;
- }
- k++;
- }
- while(i <= m) //This runs if
- {
- nums[k] = temp[i];
- k++;
- i++;
- }
- }
- }
- //This runs the mergesort Method. This is meant to be its own thread.
- class merger extends Thread
- {
- private int l;
- private int h;
- private int i;
- public merger(int lo, int hi, int in)
- {
- l = lo;
- h = hi;
- i = in;
- this.setName("merger " + in);
- }
- @Override
- public void run()
- {
- Sort.mergesort(l, h, i);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement