View source for MergeSort Parallel Combiner

=(Optional) Challenge Parallel Combiner=
{{CodeToImplement|ParallelCombiner|parallelCombine|sort.challenge.merge}}
You can divide and conquer the combine step in merge sort.  The work should remain <math>\mathcal{O}(n\lg{}n)</math> while the critical path length can be cleanly improved from <math>\mathcal{O}(n)</math> down to <math>\mathcal{O}(\lg^3{}n)</math>.

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:
* [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/current/apidocs/edu/wustl/cse231s/array/ArrayUtils.html#concat(C%5B%5D,C%5B%5D) ArrayUtils.concat(a, b)]
* [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/current/apidocs/edu/wustl/cse231s/array/ArrayUtils.html#split(C%5B%5D,int) ArrayUtils.split(array, index)]
* see spoiler

<spoiler show="spoiler" hide="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.<br/>[https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/current/apidocs/edu/wustl/cse231s/array/ArrayUtils.html#binarySearchForKeyOrInsertionPointOfKey(C%5B%5D,C,java.util.Comparator) ArrayUtils.binarySearchForKeyOrInsertionPointOfKey(array, key, comparator)]</spoiler>

==Parallel Combiner Correctness==
{{TestSuite|_ParallelMergeSortParallelCombinerTestSuite|sort.challenge.merge}}