parallel merge
**Parallel Merge Algorithms** are the **techniques for combining two sorted sequences into a single sorted sequence using multiple processors simultaneously** — a fundamental operation that underpins parallel merge sort, database merge joins, and external sorting, where the key challenge is partitioning the merge work evenly across P processors despite the data-dependent nature of merging, solved by the merge path algorithm that achieves perfect load balancing in O(log N) setup time followed by O(N/P) parallel merge work.
**Why Parallel Merge Is Hard**
- Sequential merge: Two pointers, compare-and-advance → O(N+M), inherently sequential.
- Naive parallel: Each processor takes N/P elements from each array → wrong! Merged result positions are data-dependent.
- Challenge: Where does processor k's output begin and end? Depends on the data values.
**Merge Path Algorithm (Odeh et al., 2012)**
```
Array A (sorted): [1, 3, 5, 7, 9]
Array B (sorted): [2, 4, 6, 8, 10]
Merge Matrix:
B[0]=2 B[1]=4 B[2]=6 B[3]=8 B[4]=10
A[0]=1 > > > > >
A[1]=3 < > > > >
A[2]=5 < < > > >
A[3]=7 < < < > >
A[4]=9 < < < < >
Merge path: Staircase boundary between < and >
Each step in the path = one element in merged output
```
- Merge path: Walk diagonals of the merge matrix.
- For P processors: Find P+1 evenly-spaced points on the merge path.
- Each point found by binary search on diagonal → O(log(N+M)) per processor.
- Then each processor merges its assigned segment independently → O((N+M)/P).
**GPU Merge Sort**
```cuda
// Phase 1: Sort within each thread block (small arrays)
// Use shared memory bitonic sort or odd-even merge
// Phase 2: Iteratively merge sorted blocks
for (int width = BLOCK_SIZE; width < N; width *= 2) {
// Each merge of two width-sized arrays:
// a) Binary search to find partition points (merge path)
// b) Each thread block merges one partition
merge_kernel<<>>(data, width, N);
}
```
**Merge Path Partitioning**
```cuda
__device__ void merge_path_partition(
int *A, int a_len, int *B, int b_len,
int diag, // Position on diagonal
int *a_idx, int *b_idx // Output: partition point
) {
int low = max(0, diag - b_len);
int high = min(diag, a_len);
while (low < high) {
int mid = (low + high) / 2;
if (A[mid] > B[diag - mid - 1])
high = mid;
else
low = mid + 1;
}
*a_idx = low;
*b_idx = diag - low;
}
// O(log(N+M)) binary search → perfect load balance
```
**Performance**
| Implementation | Elements | Time | Throughput |
|---------------|---------|------|------------|
| std::merge (1 core) | 100M | 450 ms | 222M elem/s |
| Parallel merge (32 cores) | 100M | 18 ms | 5.5G elem/s |
| GPU merge (A100) | 100M | 2.5 ms | 40G elem/s |
| CUB DeviceMergeSort | 100M | 8 ms | 12.5G elem/s |
**Applications**
| Application | How Merge Is Used |
|------------|------------------|
| Merge sort | Recursive split → parallel merge stages |
| Database merge join | Merge two sorted relations |
| External sort | k-way merge of sorted runs from disk |
| MapReduce shuffle | Merge sorted partitions |
| Streaming dedup | Merge sorted streams, detect duplicates |
**K-Way Merge (Multiple Sorted Arrays)**
- Binary merge tree: Merge pairs → merge results → log₂(k) rounds.
- Priority queue: Extract min from k arrays → O(N log k).
- GPU: Flatten to binary merges in tree → each level fully parallel.
Parallel merge is **the algorithmic cornerstone of parallel sorting and ordered data processing** — by solving the non-trivial problem of evenly distributing merge work across processors through the merge path technique, parallel merge enables GPU-accelerated sorting at 40+ billion elements per second, making it the key primitive behind every high-performance database engine, distributed sorting framework, and GPU sort library.