Merge-Path Partitioning: Splitting Two Sorted Runs Without Sampling

Merging two sorted runs of lengths m and n is Θ(m+n) sequential work, and unlike a reduction or a scan it cannot be split at arbitrary points: the k-th output element depends on how many elements of each input precede it, which is not known without doing the merge. Static partitioning therefore fails: giving each of P processors a contiguous share of the output requires knowing where in each input that share begins, and that is the question the merge itself answers.

The standard solution is to make the split a search problem. Merge-path partitioning computes, for a desired output position, the exact pair of input indices that produce it. The search costs O(log(min(m,n))) per split and is independent of the split points, so P−1 splits cost O(P log n) and the merge itself parallelises with no sampling error.

The path through the matrix

Picture an (m+1) × (n+1) grid. A monotone path enters at the top-left corner (0,0) and exits at (m,n), and each step moves right (consume one element of A) or down (consume one element of B). At every cell (i,j) on the path, the merge has consumed exactly i elements of A and j of B, so the path is the merge’s execution trace and the diagonal i+j = k intersects it exactly once for each output index k.

The cells where the path turns are the comparison points. The path takes a right step at (i,j) when A[i] ≤ B[j] and a down step otherwise, which is the sequential merge’s decision rule. The key observation is that the path is monotone and each diagonal contains exactly one path cell, so “where does the merge stand after k outputs” is a well-posed question with a unique answer.

Partitioning is then: for each of P−1 boundaries at output positions k = ⌈i·(m+n)/P⌉, find the path cell on the diagonal i+j = k. Each processor receives a contiguous output range and the exact input ranges that feed it, so no processor redoes work and no output appears twice.

Binary search along the diagonal

The search for diagonal k is a binary search over i, the number of A elements consumed. Given a candidate i, j = k − i. The cell is on the path when the merge would be at that point. With a merge that prefers A on ties, that condition is A[i−1] ≤ B[j] and B[j−1] < A[i]:

• If i > 0 and j < n and A[i−1] > B[j], the merge would have consumed B[j] before A[i−1], so i is too large. Move i down.
• If j > 0 and i < m and B[j−1] ≥ A[i], symmetrically, i is too small. This comparison is non-strict, and that is exactly where the tie rule lives.

The binary search narrows i over the range max(0, k−n) … min(k, m), which is the set of i values for which j is a valid index. Each probe is two comparisons, so a split costs ⌈log₂(min(m,n)+1)⌉ comparisons.

#include <stddef.h>

/* Find (i, j) with i + j == k on the merge path of sorted a[0..m) and b[0..n). */
static void merge_path_split(const int *a, size_t m, const int *b, size_t n,
                             size_t k, size_t *oi, size_t *oj)
{
    size_t lo = (k > n) ? k - n : 0;      /* j = k - i must be <= n */
    size_t hi = (k < m) ? k : m;          /* i must be <= m */
    while (lo < hi) {
        size_t i = lo + (hi - lo) / 2;    /* bias down: keeps the invariant */
        size_t j = k - i;
        if (i > 0 && j < n && a[i - 1] > b[j])
            hi = i - 1;                   /* path has not reached this i yet */
        else if (j > 0 && i < m && b[j - 1] >= a[i])
            lo = i + 1;                   /* symmetric: i too small */
        else {
            *oi = i; *oj = j;
            return;
        }
    }
    *oi = lo; *oj = k - lo;
}

The two tests are deliberately asymmetric: the A-side test is strict and the B-side test is not. When a[i−1] and b[j] are equal, the A-preferring merge takes A, so the cell is on the path; when b[j−1] and a[i] are equal, the merge would have taken a[i] first, so the cell is not. Writing the B-side test with a strict > accepts cells that the sequential merge never visits whenever the runs share a value, and the split computed from such a cell disagrees with the local merge by one element. The same tie rule must appear in the search and in every processor’s local merge, or an element lands in two output ranges or in none.

Why the split is exact

The property that makes this work is that the search is over a monotone predicate. For a fixed diagonal k, define f(i) = “the path at diagonal k has consumed at least i elements of A”. Because the path is monotone, f is monotone in i, so binary search is valid and the boundary is unique up to ties. Ties are the only ambiguity, and they are resolved by fixing the tie rule once and using it in both the search and the merge.

This contrasts with sampling-based partitioning, where a few elements are read to guess boundaries and the guess may be off by a bounded number of elements, requiring a correction pass. Merge-path partitioning has no correction pass, so the work is exactly m+n comparisons for the merge plus the split searches, which is Θ(m+n) and work-optimal. The span is Θ(log(m+n)) for the split plus Θ((m+n)/P) for the merge, so the total span is Θ((m+n)/P + log n) and the algorithm scales to P proportional to (m+n)/log n.

The same construction generalises to k-way merging. For k sorted runs, the split search becomes a search over a k-dimensional diagonal; the standard implementation does k−1 binary searches per split, each over one input against a threshold derived from the others, or uses a single binary search over the concatenated diagonal space. The cost per split rises from log n to k log n, which is why four-way and eight-way merges are the practical upper end before the split cost dominates.

Applying it to merge sort

A parallel merge sort with merge-path partitioning is a bottom-up sequence of parallel merges: pair up runs of length 1, merge each pair with P-way partitioning, then pair up runs of length 2, and so on. At each level the total work is Θ(n), the span is Θ(log n + n/P), and the number of levels is log n. Total work is Θ(n log n), span Θ(log² n + n log n / P).

The alternative is to partition the input first, sort each partition sequentially, and then merge with the same machinery. Which is better depends on where the parallel slack is: the bottom-up version has many short merges at the start (poor efficiency, since each merge of two elements is all split overhead), while the partition-first version has one sort per processor with no scheduling overhead. The partition-first shape is the one implementations tend to use, with a sequential cut-off around a few thousand elements, which relies on a sequential sort of 4096 elements being a tight, cache-resident loop.

One detail that bites in both shapes: stability. Merge-path partitioning preserves stability if and only if the tie rule is applied consistently, which means a right step is taken when A[i] ≤ B[j] and a down step only when B[j] < A[i]. Any implementation that uses ≤ in one place and < in another produces a merge that is correct as a multiset and unstable as a sequence.

Where the path model breaks

The path is defined for two sorted inputs. For inputs with duplicates the path is still monotone, but it is not unique: a run of equal values may be consumed from either input, so different tie rules yield different paths and different split indices. Any consistently applied rule gives a correct split, so the split point varies between implementations rather than between runs, and it matters only if the split indices are observed.

For external merging, where the runs do not fit in memory, the merge path is the same but the cost model is not: each probe of the binary search is a random read into a run, and log n of them per split cost more than the sequential pass over the same data even though they touch far fewer elements. The practical fix is to keep the first and last elements of each block resident and to search in block granularity first, then within a block — which is the same two-level idea as the block scan in the prefix-scan article.

For comparison-based merging of more than two runs where the runs have wildly different lengths, an unbalanced split wastes work: a processor assigned a short input range still pays the full split search. Weighting the split positions by remaining work rather than by output position keeps the balance, and the search condition becomes an inequality on the sum of the two counts rather than on their exact total.