Parallel Merge Sort
Merge sort splits an array in half, sorts each half, and merges the two sorted halves into one. The two recursive sorts are independent, so they are a natural place to run tasks in parallel.
Parallelizing the recursion
Sorting the left and right halves can happen at the same time. If we only parallelize the recursion and keep a serial merge, the merge step becomes the bottleneck because the top level merge alone touches every element serially.
Parallelizing the merge
To go faster we also split the merge. A parallel merge picks a pivot in one sorted half, uses binary search to find its rank in the other half, and merges the two resulting pieces independently:
- Each split point is found with a binary search.
- The pieces on each side of the pivot merge in parallel.
This reduces the span so the whole sort reaches a depth close to log squared of the length.
Key idea
Parallel merge sort runs the two recursive sorts at once, and splitting the merge itself removes the serial merge bottleneck.