Question

Sorting Threads Assignment

Overview

Write a multithreaded sorting program in Java which uses the merge sort algorithm. The basic steps of merge sort are: 1) divide a collection of items into two lists of equal size, 2) use merge sort to separately sort each of the two lists, and 3) combine the two sorted lists into one sorted list. Of course, if the collection of items is just asingle item then merge sort doesn’t need to perform the three steps, just return the single item. Normally, without using threads, merge sort makes a recursive call to itself to sort the first list and then another recursive call to itself to sort the second list. Instead, for this assignment, merge sort will use sorting threads to sort the list.

A sorting thread object receives the list to sort as an array via its constructor. The sorting thread class uses Java Generics in order to sort any type of object which implements the Comparable interface. For example, assume the name of the sorting thread class is MergeSort and the generic datatype name is AnyType. The sorting thread class has at the beginning of its declaration:

... class MergeSort<AnyType extends Comparable<? super AnyType>> ...and the declaration of the array of objects v to sort would look like: AnyType[] v;

A sorting thread object follows the steps of merge sort as follows: 1) divide the array of items it received into two arrays of equal size, 2) create two sorting thread objects where each thread sorts one of the equally divided arrays produced in the previous step, and 3) combine the two sorted arrays (generated by the two sorting threads from the previous step) into one sorted array. A sorting thread needs to know when each of its two sorting threads completed its execution. This is done using the join() method on each of the two sorting threads before the two sorted arrays are merged into one sorted array. Of course, if the array of items is just a single item then mergesort doesn’t need to perform the three steps, just return the single item.

Page 2 of 4

Design

1. Create a driver class and make the name of the driver class Assignment1 containing only one method:public static void main(String args[]).
   The main method itself is fairly short containing code to do the following:

   1. Create a 100 element array of Integers.

   2. Fill each element of the array with a randomly generated integer in the range of 1 to 10,000.

   3. Print the Integer array in its original unsorted order.

   4. Create a sorting thread object passing the Integer array into the sorting thread object via its constructor.

   5. Start the execution of the sorting thread.

   6. Use the join method on the sorting thread to wait until it completes its execution.

   7. Print the Integer array in its sorted order.

2. You must declare private the data members in every class you create.

3. Tip: Make your program as modular as possible, not placing all your code in one .java file. You can create as many classes as you need in addition to the classes described above. Methods being reasonably small follow the guidance that "A function do one thing, and do it well." You will lose a lot of points for codereadability if you don’t make your program as modular as possible. But, do not go overboard on creatingclasses and methods. Your common sense guides your creation of classes and methods. Though, in thisassignment you probably won’t need to create any additional classes.

4. Do NOT use your own packages in your program. If you see the keyword package on the top line of any of your .java files then you created a package. Create every .java file in the src folder of your Eclipse project

5. Do NOT use any graphical user interface code in your program!

6. Do NOT type any comments in your program. If you do a good job of programming by following the advice in number 3 above then it will be easy for me to determine the task of your code.

Answer 1

Merge Sort is a popular sorting technique which divides an array or list into two halves and then start merging them when sufficient depth is reached. Time complexity of merge sort is O(nlogn).

Threads are lightweight processes and threads shares with other threads their code section, data section and OS resources like open files and signals. But, like process, a thread has its own program counter (PC), a register set, and a stack space.

Multi-threading is way to improve parallelism by running the threads simultaneously in different cores of your processor. In this program, we’ll use 4 threads but you may change it according to the number of cores your processor has.

Examples:

Input :  83, 86, 77, 15, 93, 35, 86, 92, 49, 21, 
         62, 27, 90, 59, 63, 26, 40, 26, 72, 36
Output : 15, 21, 26, 26, 27, 35, 36, 40, 49, 59, 
         62, 63, 72, 77, 83, 86, 86, 90, 92, 93

Input :  6, 5, 4, 3, 2, 1
Output : 1, 2, 3, 4, 5, 6

package assign6;
	import java.util.*;
	/**
	* This class carries out the merge sort algorithm in parallel.
	*
	* @author Taylor Carr
	* @version 1.0
	*/
	public class ParallelMergeSorter extends Thread {
	/**
	* Sorts an array, using the merge sort algorithm.
	*
	* @param a the array to sort
	* @param comp the comparator to compare array elements
	*/
	public static <E> void sort(E[] a, Comparator<? super E> comp, int threads) {
	parallelMergeSort(a, 0, a.length-1, comp, threads);
	}
	/**
	* Sorts a range of an array, using the merge sort algorithm.
	*
	* @param a the array to sort
	* @param from the first index of the range to sort
	* @param to the last index of the range to sort
	* @param comp the comparator to compare array elements
	*/
	private static <E> void mergeSort(E[] a, int from, int to,
	Comparator<? super E> comp) {
	if (from == to) {
	return;
	}
	if (to - from >0) {
	int mid = (from + to) / 2;
	// Sort the first and the second half
	mergeSort(a, from, mid, comp);
	mergeSort(a, mid + 1, to, comp);
	merge(a, from, mid, to, comp);
	}
	}
	/**
	* Takes an array and merge sorts it in parallel if there
	* are multiple threads
	*
	* @param <E>
	* @param a is the array to sort
	* @param from is the first value to sort
	* @param to is the last value to sort
	* @param comp is the comparator that checks two numbers
	* @param availableThreads is how many threads there are to utilize
	*/
	private static <E> void parallelMergeSort(E[] a, int from, int to, Comparator<? super E> comp, int availableThreads){
	if (to - from > 0){
	if (availableThreads <=1) {
	mergeSort(a, from, to, comp);
	}
	else {
	int middle = to/2;
	Thread firstHalf = new Thread(){
	public void run(){
	parallelMergeSort(a, from, middle, comp, availableThreads - 1);
	}
	};
	Thread secondHalf = new Thread(){
	public void run(){
	parallelMergeSort(a, middle + 1, to, comp, availableThreads - 1);
	}
	};
	firstHalf.start();
	secondHalf.start();
	try {
	firstHalf.join();
	secondHalf.join();
	} catch (InterruptedException ie) {
	ie.printStackTrace();
	}
	merge(a, from, middle, to, comp);
	}
	}
	}
	/**
	* Merges two adjacent subranges of an array
	*
	* @param a the array with entries to be merged
	* @param from the index of the first element of the first range
	* @param mid the index of the last element of the first range
	* @param to the index of the last element of the second range
	* @param comp the comparator to compare array elements
	*/
	@SuppressWarnings("unchecked")
	private static <E> void merge(E[] a,
	int from, int mid, int to, Comparator<? super E> comp) {
	int n = to - from + 1;
	// Size of the range to be merged
	// Merge both halves into a temporary array b
	Object[] b = new Object[n];
	int i1 = from;
	// Next element to consider in the first range
	int i2 = mid + 1;
	// Next element to consider in the second range
	int j = 0;
	// Next open position in b
	// As long as neither i1 nor i2 past the end, move
	// the smaller element into b
	while (i1 <= mid && i2 <= to) {
	if (comp.compare(a[i1], a[i2]) < 0) {
	b[j] = a[i1];
	i1++;
	} else {
	b[j] = a[i2];
	i2++;
	}
	j++;
	}
	// Note that only one of the two while loops
	// below is executed
	// Copy any remaining entries of the first half
	while (i1 <= mid) {
	b[j] = a[i1];
	i1++;
	j++;
	}
	// Copy any remaining entries of the second half
	while (i2 <= to) {
	b[j] = a[i2];
	i2++;
	j++;
	}
	// Copy back from the temporary array
	for (j = 0; j < n; j++) {
	a[from + j] = (E) b[j];
	}
	}
	}