MergeSort Parallel Combiner

(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 ${\mathcal {O}}(n\lg {}n)$ while the critical path length can be cleanly improved from ${\mathcal {O}}(n)$ down to ${\mathcal {O}}(\lg ^{3}{}n)$.

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.

Useful methods:

• ArrayUtils.binarySearchForKeyOrInsertionPointOfKey(array, key, comparator)
• ArrayUtils.concat(a, b)
• ArrayUtils.split(array, index)

Parallel Combiner Correctness

class:	_ParallelMergeSortParallelCombinerTestSuite.java
package:	sort.challenge.merge
source folder:	testing/src/test/java