In Exercises 23.20–23.21, you reimplemented recursive sorting algorithms using the Fork/Join Framework. Why might you not want to invest the effort into applying this technique to a recursive binary search algorithm?

Exercise 23.20

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

Fig. 19.6

Exercise 23.21

Implemented the recursive quicksort algorithm. Reimplement the quicksort using the Fork/Join Framework.

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: } // method to output certain values in array private static String subarrayString(int [] data, int low, int high) { StringBuilder temporary = new StringBuilder (); 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: } split: } public static void main(String[] args) { SecureRandom generator = new SecureRandom(); merge: // output split step System.out.printf("split: %s%n". subarrayString (data, low, high)); System.out.printf(" %s%n". subarrayString (data, low, middlel)); System.out.printf(" %s%n%n", 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: // merge two sorted arrays after split calls return merge (data, low, middlel, middle2, high); merge: 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: // 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