PLEASE FOLLOW INSTRUCTIONS CAREFULLY

Problem 2: MergeSort3Way class (40)

Description:

Instead of dividing into half at each step, you are now supposed to divide recursively the initial array into thirds, sort each third, and then combine using a 3-way merge.

Please implement a MergeSort3Way class so that arrays can be sorted by using Merge Sort 3-Way.

Please read the numbers from the attached largeW.txt file into an array, apply the 3-way sorting, and output the sorted results into a file largeWResults.txt

Hint:

In the traditional Merge Sorting algorithm, we evenly divide the original array into two sub arrays, recursively sort each sub array, and then merge them into a sorting array.

To evenly divide the array into two sub-arrays, we need to find the middle index: int mid = (low+high)/2;

Now to evenly divide the array into three sub-arrays, we need to find two middle indices:

Here is one of them: int mid1 = low + (high-low)/3; Can you figure out how to find the second middle index?

Recursively sort the three sub-arrays, and then merge them (merge three sub-arrays) into one sorting array.

Starter Code:

package hw6;

class DArray {

private long[] theArray; // ref to array theArray

private int nElems; // number of data items

// -----------------------------------------------------------

public DArray(int max) // constructor

{

theArray = new long[max]; // create array

nElems = 0;

}

// -----------------------------------------------------------

public void insert(long value) // put element into array

{

theArray[nElems] = value; // insert it

nElems++; // increment size

}

// -----------------------------------------------------------

@Override

public String toString() // displays array contents

{

StringBuilder sb = new StringBuilder();

for (int j = 0; j < nElems; j++) // for each element,

sb.append(theArray[j]+" "); // display it

return sb.toString();

}

// -----------------------------------------------------------

public void mergeSort3Way() // called by main()

{

long[] workspace = new long[nElems];

recMergeSort3Way(workspace, 0, nElems-1);

}

// -----------------------------------------------------------

private void recMergeSort3Way(long[] workSpace, int low, int high) {

// YOUR CODES

}

// -----------------------------------------------------------

private void merge(long[] workSpace, int low, int mid1, int mid2, int high) {

// YOUR CODES

}

// -----------------------------------------------------------

public void writeToFile(String filename){

// YOUR CODES

// Please add the try/catch statement for file processing

}

} // end class DArray

////////////////////////////////////////////////////////////////

public class MergeSort3Way {

public static void main(String[] args){

int maxSize = 1000001; // array size

DArray arr; // reference to array

arr = new DArray(maxSize); // create the array

// Read data from the file. Please add the try/catch statement for file processing

// Invoke MergeSort3Way

// write sorted data to File.

}

}