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

// 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<<<num_blocks, threads>>>(data, width, N);
}

Merge Path Partitioning

__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

Applications

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.