The ForkJoinPool class is designed to work with divide-and-conquer algorithms: those
where a task can be recursively broken into subsets. The subsets can then be processed in
parallel, and then the results from each subset are merged into a single result. The classic ex-
ample of this is the quicksort sorting algorithm.
The important point about divide-and-conquer algorithms is that they create a lot of tasks
that must be managed by relatively few threads. Say that we want to sort an array of 10 milli-
on elements. We start by creating separate tasks to perform three operations: sort the subar-
ray containing the first 5 million elements, sort the subarray containing the second 5 million
elements, and then merge the two subarrays.
The sorting of the 5 million element arrays is similarly accomplished by sorting subarrays of
2.5 million elements and merging those arrays. This recursion continues until at some point
(e.g., when the subarray has 10 elements), it is more efficient to use insertion sort on the ar-
ray and sort it directly. Figure 9-1 shows how that all works out.