MergeSort Parallel Combiner

From CSE231 Wiki
Jump to: navigation, search

(Optional) Challenge Parallel Combiner

class: Java.png
methods: parallelCombine
package: sort.challenge.merge
source folder: 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).

Circle-information.svg 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.
Attention niels epting.svg Warning: SPOILER: Arrays.binarySearch(a) returns a negative number if it does not find the exact number.

Parallel Combiner Correctness

class: Junit.png
package: sort.challenge.merge
source folder: src/test/java