Merge Path Search

Merge path search finds partition points in two sorted arrays so that a merge can be split into independent chunks. It is mainly used for parallel merge, GPU merge, and distributed sorted data processing.

The method views merging as a path through a grid. Each step consumes one element from either the first array or the second array. A diagonal in this grid represents a fixed number of merged output elements.

Problem

Given two sorted arrays $A$ and $B$ , find indices $i$ and $j$ such that:

i + j = k

and the first $k$ elements of the merged output come from:

A[0:i] \quad \text{and} \quad B[0:j]

The pair $(i, j)$ is the merge partition for output position $k$ .

Idea

For a fixed output rank $k$ , we need a split:

j = k - i

The split is valid when:

A[i - 1] \le B[j]

and

B[j - 1] \le A[i]

Boundary cases treat missing values as negative or positive infinity.

Because increasing $i$ decreases $j$ , the validity condition is monotone. We can binary search for the correct $i$ .

Algorithm

merge_path_search(A, B, k):
    low = max(0, k - length(B))
    high = min(k, length(A))

    while low <= high:
        i = (low + high) // 2
        j = k - i

        if i > 0 and j < length(B) and A[i - 1] > B[j]:
            high = i - 1
        elif j > 0 and i < length(A) and B[j - 1] > A[i]:
            low = i + 1
        else:
            return (i, j)

Example

Let:

A = [2, 6, 9, 13]

B = [1, 4, 8, 10, 15]

Find the partition for:

k = 5

The first five merged elements are:

[1, 2, 4, 6, 8]

So the split is:

i = 2,\quad j = 3

because:

A[0:2] = [2, 6]

and:

B[0:3] = [1, 4, 8]

Check:

condition	value
$A[i - 1] \le B[j]$	$6 \le 10$
$B[j - 1] \le A[i]$	$8 \le 9$

Both hold, so $(2, 3)$ is valid.

Correctness

The algorithm searches over possible values of $i$ . For each candidate, $j$ is fixed by $j = k - i$ .

If $A[i - 1] > B[j]$ , then too many elements were taken from $A$ , so high moves left. If $B[j - 1] > A[i]$ , then too few elements were taken from $A, so low` moves right.

When neither condition holds, all elements before the partition are less than or equal to all elements after the partition. Therefore the split gives exactly the first $k$ merged elements.

Complexity

operation	time
one partition search	$O(\log \min(	A	,	B	))$
$p$ partitions	$O(p \log \min(	A	,	B	))$

Space:

O(1)

For parallel merge, each worker gets an output range $[k_1, k_2)$ and computes two merge path searches to find its input ranges.

When to Use

Use merge path search when:

two sorted arrays must be merged
merge work should be split evenly
parallel workers need independent ranges
GPU threads need balanced merge partitions
output positions matter directly

It is a core primitive for parallel merge sort and high throughput sorted joins.

Implementation

def merge_path_search(a, b, k):
    low = max(0, k - len(b))
    high = min(k, len(a))

    while low <= high:
        i = (low + high) // 2
        j = k - i

        if i > 0 and j < len(b) and a[i - 1] > b[j]:
            high = i - 1
        elif j > 0 and i < len(a) and b[j - 1] > a[i]:
            low = i + 1
        else:
            return i, j

    return low, k - low

func MergePathSearch(a []int, b []int, k int) (int, int) {
    low := 0
    if k-len(b) > low {
        low = k - len(b)
    }

    high := k
    if len(a) < high {
        high = len(a)
    }

    for low <= high {
        i := (low + high) / 2
        j := k - i

        if i > 0 && j < len(b) && a[i-1] > b[j] {
            high = i - 1
        } else if j > 0 && i < len(a) && b[j-1] > a[i] {
            low = i + 1
        } else {
            return i, j
        }
    }

    return low, k - low
}