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?"

Useful methods:

• ArrayUtils.concat(a, b)
• ArrayUtils.split(array, index)
• see spoiler

You can divide one side (for guaranteed performance, choose the longer of the two) and then binary search for the value in the other side.
ArrayUtils.binarySearchForKeyOrInsertionPointOfKey(array, key, comparator)

Parallel Combiner Correctness

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