Question

Write a multithreaded sorting program that works as follows: A list of integers

is divided into two smaller lists of equal size. Two separate threads (which we

will term sorting threads) sort each sublist using a sorting algorithm of your

choice. The two sublists are then merged by a third thread—a merging thread

—which merges the two sublists into a single sorted list.

Because global data are shared cross all threads, perhaps the easiest way

to set up the data is to create a global array. Each sorting thread will work on

one half of this array. A second global array of the same size as the unsorted

integer array will also be established. The merging thread will then merge

the two sublists into this second array. Graphically, this program is structured

according to Figure 4.20.

This programming project will require passing parameters to each of the

sorting threads. In particular, it will be necessary to identify the starting index

from which each thread is to begin sorting. Refer to the instructions in Project

1 for details on passing parameters to a thread.

The parent thread will output the sorted array once all sorting threads have

exited.

**In JAVA**

Answer 1

Code //Package name package mergesortthread; import java.util.logging.Logger; import java.util.logging. Level; //Class MergeSortThread public class MergeSortThread implements Runnable / /Needed variables private final int first; private final int last; //Constructor public MergeSortThread (int f, int 1) this. first = f; this.last- l; //Method run () GOverride public void run () //Try. try //Function call MyMergeSort.mergesortmethod (first, last); //Catchh catch (InterruptedException ieEx) //Exception Logger.getLogger (MergeSortThread.class.getName ()) log (Level. SEVERE, null, ieEx); //Package name package mergesortthread; //Class public class MyMergeSort / /Needed variables private static volatile int[] inputs; private static volatile int[] temp; private int input;

//Method mysort () public void mysort (int[] inputValues) throws InterruptedException MyMergesort.inputs = inputvalues; input = inputvalues. length; MyMergeSort.temp new int[input]; mergesortmethod (0, input - 1); //Method mergesortmethod () public static void mergesortmethod (int lo, InterruptedException int hi)throws //Condition check //Whether low is lesser than high or not. If not sort array if (lo < hi) //Get index of input which is in mid int mid = 1 + (hi - lo) / 2; //Sort left array Thread tLeft = new Thread(new MergeSortThread(lo, mid)); //Sort right array Thread tRight = new Thread (new MergesortThread (mid+ 1 , hi)); tLeft.start ); tRight.start ) tLeft.join); tRight.join () //Merge sides myMerger (lo, mid, hi) //Method myMerger private static void myMerger (int lo, int mid, int hi) //Copy both the sides in temp array for (int 11 = lo; 11 <= hi; 11++) temp [ і 1 ] inputs [ 11 ] ; = //Update the ії, i2, i3 values int 11 = 10; int 12 = mid 1; int 13 = 10; //Copy the least value from either left or right And place in original array if (temp [il] <- temp [i2])

inputs [13] temp[11]; else inputs [13] i2++; = temp [12]; 13++ //Copy rest of left side of array while (i1 〈= mid) inputs [13] 13++ = temp[11]; //Method Main () public static void main (String[] args) throws InterruptedException //Input int[] array = new int [10]; //For loop to iterate for (int pos-0; pos<10 pos++) array[pos] 10-pos long inputStart- System.currentTimeMillis(); //Function call new MyMergeSort ().mysort (array); long inputEnd - System.currentTimeMillis( //For loop to print the output for (int 11 0; il array.length; il++) System.out.print (array[il]+" ") //Print newline System.out.println("\n"); System.out.println ("Time taken in milliseconds: "+(inputEnd inputStart)+"\n\n") ,;

Sample Output Output MergeSortThread (run) a zun: 1 2 3 4 5 6 7 8 9 10 ル! Time taken in milliseconds: 0 BUILD SUCCESSFUL (total time: 0 seconds)

Executable Code

//Package name.
package mergesortthread;
import java.util.logging.Logger;
import java.util.logging.Level;

//Class MergeSortThread
public class MergeSortThread implements Runnable
{

   
    //Needed variables.
    private final int first;
    private final int last;

    //Constructor.
    public MergeSortThread(int f, int l)
    {
        this.first = f;
        this.last = l;
    }

    //Method run().
    @Override
    public void run()
    {
       
        //Try.
        try
        {
           
            //Function call.
            MyMergeSort.mergesortmethod(first, last);
        }
       
        //Catch.
        catch (InterruptedException ieEx)
        {
          
           //Exception.
           Logger.getLogger(MergeSortThread.class.getName()).log(Level.SEVERE, null, ieEx);
        }
    }
}


//Package name.
package mergesortthread;

//Class.
public class MyMergeSort
{
   
    //Needed variables.
    private static volatile int[] inputs;
    private static volatile int[] temp;
    private int input;

    //Method mysort().
    public void mysort(int[] inputValues) throws InterruptedException
    {
        MyMergeSort.inputs = inputValues;
        input = inputValues.length;
        MyMergeSort.temp = new int[input];
        mergesortmethod(0, input - 1);
    }

    //Method mergesortmethod().
    public static void mergesortmethod(int lo, int hi) throws InterruptedException
    {
       
        //Condition check
        //Whether low is lesser than high or not. If not sort array.
        if (lo < hi)
        {
           
            //Get index of input which is in mid.
            int mid = lo + (hi - lo) / 2;
           
            //Sort left array.
            Thread tLeft = new Thread(new MergeSortThread(lo, mid));
           
            //Sort right array.
            Thread tRight = new Thread(new MergeSortThread(mid+1, hi));

            tLeft.start();
            tRight.start();
            tLeft.join();
            tRight.join();

            //Merge sides.
            myMerger(lo, mid, hi);
        }
    }

    //Method myMerger().
    private static void myMerger(int lo, int mid, int hi)
    {
       
        //Copy both the sides in temp array.
        for (int i1 = lo; i1 <= hi; i1++)
        {
           temp[i1] = inputs[i1];
        }

        //Update the i1, i2, i3 values.
        int i1 = lo;
        int i2 = mid + 1;
        int i3 = lo;
       
        //Copy the least value from either left or right
        //And place in original array.
        while (i1 <= mid && i2 <= hi)
        {
            if (temp[i1] <= temp[i2])
            {
                inputs[i3] = temp[i1];
                i1++;
            }
            else
            {
                inputs[i3] = temp[i2];
                i2++;
            }
            i3++;
        }
        //Copy rest of left side of array.
        while (i1 <= mid)
        {
            inputs[i3] = temp[i1];
            i3++;
            i1++;
        }
    }

    //Method Main().
    public static void main(String[] args) throws InterruptedException
    {
       
        //Input.
        int[] array = new int[10];
       
        //For loop to iterate.
        for(int pos = 0; pos<10; pos++)
        {
            array[pos] = 10-pos;
        }
        long inputStart = System.currentTimeMillis();
       
        //Function call.
        new MyMergeSort().mysort(array);
        long inputEnd = System.currentTimeMillis();
       
        //For loop to print the output.
        for(int i1 = 0; i1<array.length; i1++)
        {
            System.out.print(array[i1]+" ");
        }
       
        //Print newline.
        System.out.println("\n");
        System.out.println("Time taken in milliseconds: " +(inputEnd-inputStart)+"\n\n");
    }
}