Demonstrated the recursive merge sort algorithm. Reimplement the program of Fig. 19.6 using the Fork/Join Framework.

Fig. 19.6

Transcribed Image Text:

I // Fig. 19.6: MergeSortTest.java // Sorting an array with merge sort. import java.security.SecureRandom; 2 4 import java.util.Arrays; 6 public class MergeSortTest { 7 12 14 15 16 17 18 19 20 27 28 29 30 31 32 33 35 36 37 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 III 112 113 114 } // calls recursive sortArray method to begin merge sorting public static void mergeSort (int[] data) { sortArray (data, 0, data.length - 1); // sort entire array } // splits array, sorts subarrays and merges subarrays into sorted array private static void sortArray (int[] data, int low, int high) { // test base case; size of array equals 1 } } // merge two sorted subarrays into one sorted subarray private static void merge(int[] data, int left, int middlel, int middle2, int right) { split: split: merge: merge: split: merge: merge: split: split: split: merge: if ((high low) >= 1) { // if not base case. int middle1 = (low + high) / 2; // calculate middle of array int middle2 = middlel + 1; // calculate next element over merge: } } // method to output certain values in array private static String subarrayString(int[] data, int low, int high) { StringBuilder temporary = new StringBuilder(); split: merge: // output split step System.out.printf("split: subarrayString(data, System.out.printf(" subarrayString(data, System.out.printf(" subarrayString(data, middle2, high)); //split array in half; sort each half (recursive calls) sortArray (data, low, middlel); // first half of array sortArray (data, middle2, high); // second half of array merge: } public static void main(String[] args) { SecureRandom generator = new SecureRandom(); merge: // merge two sorted arrays after split calls return merge (data, low, middlel, middle2, high); int leftIndex = left; // index into left subarray int rightIndex = middle2; // index into right subarray int combinedIndex = left; // index into temporary working array int[] combined = new int[data.length]; // working array } Unsorted array: [75, 56, 85, 90, 49, 26, 12, 48, 40, 47] split: split: 75 56 85 90 49 75 56 85 // output two subarrays before merging System.out.printf("merge: %s%n", subarrayString(data, left, middlel)); System.out.printf(" %s%n", subarrayString(data, middle2, right)); // merge arrays until reaching end of either while (leftIndex