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;

import java.io.IOException; import java.io.FileNotFoundException; import java.util.Scanner; import java.io.File; import java.io.FileWriter;

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) { if (low == high) return;

int oneThird = (high - low) / 3;

// find the middle indices int mid1 = low + oneThird; int mid2 = low + oneThird * 2;

// sort each sub-array recMergeSort3Way(workSpace, low, mid1); recMergeSort3Way(workSpace, mid1 + 1, mid2); recMergeSort3Way(workSpace, mid2 + 1, high);

// merge the three sub-arrays merge(workSpace, low, mid1, mid2, high); } // -----------------------------------------------------------

private void merge(long[] workSpace, int low, int mid1, int mid2, int high) { int i = low; int j = mid1 + 1; int k = mid2 + 1; int l = 0;

while (i <= mid1 && j <= mid2 && k <= high) { if (theArray[i] < theArray[j]) { if (theArray[i] < theArray[k]) { workSpace[l++] = theArray[i++]; } else { workSpace[l++] = theArray[k++]; } } else { if (theArray[j] < theArray[k]) { workSpace[l++] = theArray[j++]; } else { workSpace[l++] = theArray[k++]; } } }

while (i <= mid1 && j <= mid2) { if (theArray[i] < theArray[j]) { workSpace[l++] = theArray[i++]; } else { workSpace[l++] = theArray[j++]; } }

while (j <= mid2 && k <= high) { if (theArray[j] < theArray[k]) { workSpace[l++] = theArray[j++]; } else { workSpace[l++] = theArray[k++]; } }

while (i <= mid1 && k <= high) { if (theArray[i] < theArray[k]) { workSpace[l++] = theArray[i++]; } else { workSpace[l++] = theArray[k++]; } }

while (i <= mid1) { workSpace[l++] = theArray[i++]; }

while (j <= mid2) { workSpace[l++] = theArray[j++]; }

while (k <= high) { workSpace[l++] = theArray[k++]; }

for (int m = 0; m < l; m++) { theArray[low + m] = workSpace[m]; } } // -----------------------------------------------------------

public void writeToFile(String filename) { try { FileWriter writer = new FileWriter(filename); for (int j = 0; j < nElems; j++) { writer.write(theArray[j] + " "); } writer.close(); } catch (IOException e) { e.printStackTrace(); } } } // end class DArray ////////////////////////////////////////////////////////////////

public class MergeSort3Way { public static void main(String[] args) { int maxSize = 1000001; DArray arr; arr = new DArray(maxSize);

String filename = "largeW.txt"; try { Scanner scanner = new Scanner(new File(filename)); while (scanner.hasNextLong()) { long value = scanner.nextLong(); arr.insert(value); } scanner.close(); } catch (FileNotFoundException e) { e.printStackTrace(); return; }

arr.mergeSort3Way();

String outputFilename = "largeWResults.txt"; arr.writeToFile(outputFilename); } }