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);
}
}