QuestionQuestion

Sorting is a compute-intensive activity and mergesort is a sorting algorithm that can be fairly easily parallelised. So, this exercise aims to implement a parallel version of mergesort and evaluate its performance on the multicore machine mcore48. All development of code should be done on a normal teaching domain machine, so that usage of the multicore machine is minimised.
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 PreviewSolution 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++;...
$60.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats