Implement the merge sort algorithm of Chapter 14 by spawning a new thread for ea
ID: 3536192 • Letter: I
Question
Implement the merge sort algorithm of Chapter 14 by spawning a
new thread
for each smaller MergeSorter. Hint: Use the join method of the
Thread class to wait
for the spawned threads to finish. Look up the
method’s behavior in the API
documentation.
Here is the merge sort algorithm
/**
This class sorts an array, using the merge sort algorithm.
*/
public class MergeSorter
{
private int[] a;
/**
Constructs a merge sorter.
@param anArray the array to sort
*/
public MergeSorter(int[] anArray)
{
a = anArray;
}
/**
Sorts the array managed by this merge sorter.
*/
public void sort()
{
if (a.length <= 1) return;
int[] first = new int[a.length / 2];
int[] second = new int[a.length - first.length];
// Copy the first half of a into first, the second half into second
for (int i = 0; i < first.length; i++) { first[i] = a[i]; }
for (int i = 0; i < second.length; i++)
{
second[i] = a[first.length + i];
}
MergeSorter firstSorter = new MergeSorter(first);
MergeSorter secondSorter = new MergeSorter(second);
firstSorter.sort();
secondSorter.sort();
merge(first, second);
}
/**
Merges two sorted arrays into the array managed by this merge sorter.
@param first the first sorted array
@param second the second sorted array
*/
private void merge(int[] first, int[] second)
{
int iFirst = 0; // Next element to consider in the first array
int iSecond = 0; // Next element to consider in the second array
int j = 0; // Next open position in a
// As long as neither iFirst nor iSecond is past the end, move
// the smaller element into a
while (iFirst < first.length && iSecond < second.length)
{
if (first[iFirst] < second[iSecond])
{
a[j] = first[iFirst];
iFirst++;
}
else
{
a[j] = second[iSecond];
iSecond++;
}
j++;
}
// Note that only one of the two loops below copies entries
// Copy any remaining entries of the first array
while (iFirst < first.length)
{
a[j] = first[iFirst];
iFirst++; j++;
}
// Copy any remaining entries of the second half
while (iSecond < second.length)
{
a[j] = second[iSecond];
iSecond++; j++;
}
}
}
Explanation / Answer
public class MergeSorter extends Thread
{
private int[] a;
/**
* Constructs a merge sorter.
*
* @param anArray
* the array to sort
*/
public MergeSorter(int[] anArray)
{
a = anArray;
}
/**
* Sorts the array managed by this merge sorter.
*/
public void sort()
{
if (a.length <= 1)
return;
int[] first = new int[a.length / 2];
int[] second = new int[a.length - first.length];
// Copy the first half of a into first, the second half into second
for (int i = 0; i < first.length; i++) {
first[i] = a[i];
}
for (int i = 0; i < second.length; i++)
{
second[i] = a[first.length + i];
}
MergeSorter firstSorter = new MergeSorter(first);
MergeSorter secondSorter = new MergeSorter(second);
firstSorter.sort();
secondSorter.sort();
merge(first, second);
}
/**
* Merges two sorted arrays into the array managed by this merge sorter.
*
* @param first
* the first sorted array
* @param second
* the second sorted array
*/
private void merge(int[] first, int[] second)
{
int iFirst = 0; // Next element to consider in the first array
int iSecond = 0; // Next element to consider in the second array
int j = 0; // Next open position in a
// As long as neither iFirst nor iSecond is past the end, move
// the smaller element into a
while (iFirst < first.length && iSecond < second.length)
{
if (first[iFirst] < second[iSecond])
{
a[j] = first[iFirst];
iFirst++;
}
else
{
a[j] = second[iSecond];
iSecond++;
}
j++;
}
// Note that only one of the two loops below copies entries
// Copy any remaining entries of the first array
while (iFirst < first.length)
{
a[j] = first[iFirst];
iFirst++;
j++;
}
// Copy any remaining entries of the second half
while (iSecond < second.length)
{
a[j] = second[iSecond];
iSecond++;
j++;
}
}
public void run() {
sort();
}
public int[] getA(){
return a;
}
public static void main(String[] args) throws InterruptedException {
MergeSorter mergeSorter1 = new MergeSorter(new int[]{2,5,7,1,4,3});
MergeSorter mergeSorter2 = new MergeSorter(new int[]{25,51,67,11,40,34});
MergeSorter mergeSorter3 = new MergeSorter(new int[]{12,55,17,13,44,23});
mergeSorter1.start();
mergeSorter1.join();
System.out.println("After sorting array1:");
for(int i: mergeSorter1.getA()){
System.out.print(i + " ");
}
mergeSorter2.start();
mergeSorter2.join();
System.out.println(" After sorting array2:");
for(int i: mergeSorter2.getA()){
System.out.print(i + " ");
}
mergeSorter3.start();
mergeSorter3.join();
System.out.println(" After sorting array3:");
for(int i: mergeSorter3.getA()){
System.out.print(i + " ");
}
}
}
output:
After sorting array1:
1 2 3 4 5 7
After sorting array2:
11 25 34 40 51 67
After sorting array3:
12 13 17 23 44 55