Java Reference
In-Depth Information
Figure 9-1. Tasks in a recursive quicksort
In the end, there will be more than 1 million tasks to sort the leaf arrays (each of which will
be smaller than 10 elements—the point at which sorting them directly makes sense). (The ac-
tual value for that varies by implementation; 10 is just used for illustration here. Current ver-
sions of Java use insertion sort when the array size is less than 47 elements.) More than
500,000 tasks are needed to merge those sorted arrays, 250,000 tasks to merge the next set of
sorted arrays, and so on. In the end, there will be 2,097,151 tasks.
The larger point here is that none of the tasks can complete until the tasks that they have
spawned have also completed. The tasks directly sorting arrays of less than 10 elements must
be completed first, and then tasks can merge the two small arrays that they created, and so
on: everything is merged up the chain until the entire array is merged into its final, sorted
value.
Search WWH ::




Custom Search