Question

I have a multithreaded java sorting program that works as follows:

1. A list of double values is divided into two smaller lists of equal size

2. Two separate threads (which we will term sorting threads) sort each sublist using a sorting algorithm of your choice

3. The two sublists are then merged by a third thread merging thread that merges the two sublists into a single sorted list.

SIMPLE EXECUTION

>java SortParallel 1000
Sorting is done in 8.172561ms when two threads are used
Sorting is done in 8.044095ms when one thread is used

I need to extend my program so it can take another command line parameter, T (an even integer). Then it creates T threads instead of just 2 and gives 1/T of the array to each thread to sort and then merge! And see how increasing the number of threads affects the execution time.

Here is existing code:

/* SortParallel.java */
import java.util.*;

class MergeThread extends Thread {
private double[] in ; // the input array
private double[] out; // the output array
private int mid; // dividing point into subarrays

public MergeThread(double[] i, double[] o, int m) { in = i;
out = o;
mid = m;
}

public void run() {
int i, j, k;
//System.out.println("Merge " + in.length + " : ");
i = k = 0;
j = mid;
while (i < mid && j < in .length) {
if ( in [i] < in [j])
out[k++] = in [i++];
else
out[k++] = in [j++];
}
while (i < mid)
out[k++] = in [i++];
while (j < in .length)
out[k++] = in [j++];
/*for(i = 0; i < in.length; i++)
System.out.print(" " + out[i]);
System.out.println(""); */
}
};

class SortThread extends Thread {
private double[] arr; // the array to be sorted
private int beg, end; // The start, end points in the array to be sorted

public SortThread(double[] a, int b, int e) {
arr = a;
beg = b;
end = e;
}

public void run() {
int i, j, min;
double tmp;
arr = arr;
//System.out.println("sort " + beg + " to " + end);
for (i = beg; i < end; i++) {
min = i;
for (j = i + 1; j < end; j++) {
if (arr[j] < arr[min])
min = j;
}
tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
/*for(i = beg; i < end; i++)
System.out.print(" " + arr[i]);
System.out.println("\nEnd sort"); */
}
};
public class SortParallel {

public static void main(String[] arg) {
int mid, N, i;

double[] arr; /* array */
double[] arr2; /* Used for a copy */
double[] merged; /* For storing the merged array */

long start, diff;
/* I NEED ONE EXTRA PARAMETER HERE */
if (arg.length != 1) {
System.out.println("Usage: java SortParallel ");
return;
}

N = Integer.parseInt(arg[0]);
arr = new double[N];
arr2 = new double[N];
merged = new double[N];

Random rand = new Random(System.currentTimeMillis());

//System.out.println ("Array: ");
for (i = 0; i < N; i++) {
/* generate random numbers */
arr[i] = arr2[i] = rand.nextDouble() * 99.0 + 1.0; /* range 1.0 - 100.0 */
//System.out.print(" "+ arr[i]);
}
//System.out.println("");

//Create threads
SortThread sort1 = new SortThread(arr, 0, N / 2);
SortThread sort2 = new SortThread(arr, N / 2, arr.length);
MergeThread merge1 = new MergeThread(arr, merged, N / 2);

start = System.nanoTime(); /* start time */

/* Start the threads for working on sub arrays */
sort1.start();
sort2.start();

/* Wait for sorting to complete */
try {
sort1.join();
sort2.join();
} catch (Exception e) {
e.printStackTrace();
}

/* Start thread for merge */
merge1.start();
/* Wait for merge thread to complete */
try {
merge1.join();
} catch (Exception e) {
e.printStackTrace();
}

diff = System.nanoTime() - start; /* End time */

System.out.println("Sorting is done in " + diff / 1000000.0f + "ms when two threads are used");

SortThread sortComplete = new SortThread(arr2, 0, N); /* To run on the whole array */

start = System.nanoTime(); /* start time */

sortComplete.start();
try {
sortComplete.join();
} catch (Exception e) {
e.printStackTrace();
}

diff = System.nanoTime() - start; /* End time */

System.out.println("Sorting is done in " + diff / 1000000.0f + "ms when one thread is used");
}
}

Please do the needful.

Answer 1

> <terminated> SortParallel [Java Application] C:\Program Files\ava\jdk1. Sorting is done in 0.6813ms when 4 threads are used start = System.nanoTime(); /* start time */ // Now array is sorted. // wait for threads to join. for (i = 0; i < numThreads; i++) | try { threads[i].join(); } catch (InterruptedException e) { e.printStackTrace(); } } int threadCount = numThreads; while(threadCount != 1) { threadCount = threadCount/2; MergeThread mergeThreads[] = new MergeThread[thread Count]; 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 startIndex = 0; for (i = 0; i < threadCount; i++) { if(i != threadCount-1) { merge Threads[i] = new MergeThread(arr, merged, startIndex, startIndex + subSize, startIndex } else { merge Threads[i] = new Merge Thread(arr, merged, startIndex, startIndex + subSize, arr.length ہا startIndex += 2 * subSize; نہا for (i = 0; i < threadCount; i++) { merge Threads[i].start(); نہا // switch arr. and merged, as we need a temporary array to copy the data back. double tmp[] = arr; arr = merged; merged = tmp; subSize = subSize * 2; } // Uncomment below to see the array // System.out.println(Arrays.toString(arr)); diff = System.nanoTime() - start; /* End time */

import java.util.*;

class MergeThread extends Thread {
    private double[] in; // the input array
    private double[] out; // the output array
    private int mid, start, end; // dividing point into subarrays

    public MergeThread(double[] i, double[] o, int start, int mid, int end) {
        in = i;
        out = o;
        this.start = start;
        this.mid = mid;
        this.end = end;
    }

    public void run() {
        int i, j, k;
        i = k = start;
        j = mid;
        while (i < mid && j < end) {
            if (in[i] < in[j])
                out[k++] = in[i++];
            else
                out[k++] = in[j++];
        }
        while (i < mid)
            out[k++] = in[i++];
        while (j < end)
            out[k++] = in[j++];
    }
};

class SortThread extends Thread {
    private double[] arr; // the array to be sorted
    private int beg, end; // The start, end points in the array to be sorted

    public SortThread(double[] a, int b, int e) {
        arr = a;
        beg = b;
        end = e;
    }

    public void run() {
        int i, j, min;
        double tmp;

        for (i = beg; i < end; i++) {
            min = i;
            for (j = i + 1; j < end; j++) {
                if (arr[j] < arr[min])
                    min = j;
            }
            tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }
};

public class SortParallel {

    public static void main(String[] arg) {
        int arrSize, i;
        int numThreads;
        
        double[] arr; /* array */
        double[] merged; /* For storing the merged array */

        long start, diff;

        /* I NEED ONE EXTRA PARAMETER HERE */
        if (arg.length != 2) {
            System.out.println("Usage: java SortParallel <ArraySize> <NumThreads>");
            return;
        }

        // numThreads should be a power of 2, and Similarly, the array size should be divisible by numThreads
        arrSize = Integer.parseInt(arg[0]);
        numThreads = Integer.parseInt(arg[1]);

        arr = new double[arrSize];
        merged = new double[arrSize];

        Random rand = new Random(System.currentTimeMillis());

        for (i = 0; i < arrSize; i++) {
            arr[i] = rand.nextDouble() * 99.0 + 1.0; /* range 1.0 - 100.0 */
        }
        
        int subSize = arrSize / numThreads;

        SortThread threads[] = new SortThread[numThreads];
        int startIndex = 0;
        for (i = 0; i < numThreads - 1; i++) {
            threads[i] = new SortThread(arr, startIndex, startIndex + subSize);
            threads[i].start();
            startIndex += subSize;
        }
        threads[i] = new SortThread(arr, startIndex, arrSize);
        threads[i].start();

        start = System.nanoTime(); /* start time */
        // Now array is sorted.

        // wait for threads to join.
        for (i = 0; i < numThreads; i++) {
            try {
                threads[i].join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        
        int threadCount = numThreads;
        while(threadCount != 1) {
            threadCount = threadCount/2;
            MergeThread mergeThreads[] = new MergeThread[threadCount];
            
            startIndex = 0;
            for (i = 0; i < threadCount; i++) {
                if(i != threadCount-1) {
                    mergeThreads[i] = new MergeThread(arr, merged, startIndex, startIndex + subSize, startIndex + 2*subSize);
                } else {
                    mergeThreads[i] = new MergeThread(arr, merged, startIndex, startIndex + subSize, arr.length);
                }
                startIndex += 2 * subSize;
            }
            
            for (i = 0; i < threadCount; i++) {
                mergeThreads[i].start();
            }
            
            // switch arr and merged, as we need a temporary array to copy the data back.
            double tmp[] = arr;
            arr = merged;
            merged = tmp;
            subSize = subSize * 2;
        }
        
        // Uncomment below to see the array
        // System.out.println(Arrays.toString(arr));

        diff = System.nanoTime() - start; /* End time */

        System.out.println("Sorting is done in " + diff / 1000000.0f + "ms when " + numThreads + " threads are used");
    }
}

**************************************************

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.