(Optional) Challenge Parallel Combiner
class: |
ParallelCombiner.java |
|
methods: |
parallelCombine |
package: |
sort.challenge.merge |
source folder: |
student/src/main/java |
You can divide and conquer the combine step in merge sort. The work should remain while the critical path length can be cleanly improved from down to .
Sadly, you cannot simply divide both sides down the middle and merge the lower halves together and the upper halves together (as the data will likely not line up perfectly).
Tip:Being able to perform operations like merge sort combine in parallel often comes down to the question "How can I figure out where to put the current item?" |
You can divide one side (choose the longer of the two) and then binary search for the value in the other side. Note:
Arrays.binarySearch(a) returns a negative number if it does not find the exact number.
Parallel Combiner Correctness
class: |
_ParallelMergeSortParallelCombinerTestSuite.java |
|
package: |
sort.challenge.merge |
source folder: |
testing/src/test/java |