## Question

Algorithm

Some pseudocode is given below:

int[] mergesort(int[] inArray, int start, int end, int numThreads)

{

if (numThreads > 1)

{

spawn a new thread to sort the first half ...

res1 = mergesort(inArray, start, (start+end)/2, numThreads/2);

meanwhile continue sorting the other half ...

res2 = mergesort(inArray, (start+end)/2 + 1, end, numThreads/2);

join with spawned thread;

generate result by merging res1 with res2;

}

else

{

generate result between start and end (inclusive) using

a sequential sort method on inArray;

}

return result; }

Note that the sort should be conducted in-place, that is, the parallel half sorts should modify the same (shared) copy of inArray. This is possible because the two half sorts are completely independent of one another. The recommended sequential sort method is that provided by Java.utils.Arrays. It is suggested that the numbers to be sorted should be alternately taken from an ascending sequence starting at 1 and a descending sequence starting at n/2, where n is the length of inArray Use System.nanoTime() to record the times (in nanoseconds) before the sorting commences and after it has been completed, and hence print the time needed to perform the computation.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

package hmwrk;import java.util.*; // for Random

public class MergeSort {

private static final Random RAND = new Random(42); // random number generator

public static void main(String[] args) throws Throwable {

int LENGTH = 1000; // initial length of array to sort

int RUNS = 16; // how many times to grow by 2?

for (int i = 1; i <= RUNS; i++) {

int[] a = createRandomArray(LENGTH);

// run the algorithm and time how long it takes

long startTime1 = System.nanoTime();

parallelMergeSort(a);

long endTime1 = System.nanoTime();

if (!isSorted(a)) {

throw new RuntimeException("not sorted afterward: " + Arrays.toString(a));

}

System.out.printf("%10d elements => %6d nano seconds \n", LENGTH, endTime1 - startTime1);

LENGTH *= 2; // double size of array for next time

}

}

public static void parallelMergeSort(int[] a) {

// int cores = Runtime.getRuntime().availableProcessors();

int cores = 8;

parallelMergeSort(a, cores);

}

public static void parallelMergeSort(int[] a, int threadCount) {

if (threadCount <= 1) {

mergeSort(a);

} else if (a.length >= 2) {

// split array in half

int[] left = Arrays.copyOfRange(a, 0, a.length / 2);

int[] right = Arrays.copyOfRange(a, a.length / 2, a.length);

// sort the halves

// mergeSort(left);

// mergeSort(right);

Thread lThread = new Thread(new Sorter(left, threadCount / 2));

Thread rThread = new Thread(new Sorter(right, threadCount / 2));

lThread.start();

rThread.start();

try {

lThread.join();

rThread.join();

} catch (InterruptedException ie) {}

// merge them back together

merge(left, right, a);

}

}

// Arranges the elements of the given array into sorted order

// using the "merge sort" algorithm, which splits the array in half,

// recursively sorts the halves, then merges the sorted halves.

// It is O(N log N) for all inputs.

public static void mergeSort(int[] a) {

if (a.length >= 2) {

// split array in half

int[] left = Arrays.copyOfRange(a, 0, a.length / 2);

int[] right = Arrays.copyOfRange(a, a.length / 2, a.length);

// sort the halves

mergeSort(left);

mergeSort(right);

// merge them back together

merge(left, right, a);

}

}

// Combines the contents of sorted left/right arrays into output array a.

// Assumes that left.length + right.length == a.length.

public static void merge(int[] left, int[] right, int[] a) {

int i1 = 0;

int i2 = 0;

for (int i = 0; i < a.length; i++) {

if (i2 >= right.length || (i1 < left.length && left[i1] < right[i2])) {

a[i] = left[i1];

i1++;

} else {

a[i] = right[i2];

i2++;...