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