Merging two sorted arrays is a prominent building block for sorting and other functions.

Its ecient parallelization requires balancing the load among compute cores, minimizing the

extra work brought about by parallelization, and minimizing inter-thread synchronization

requirements. Ecient use of memory is also important.

Merging two sorted arrays is a prominent building block for sorting and other functions.

Its ecient parallelization requires balancing the load among compute cores, minimizing the

extra work brought about by parallelization, and minimizing inter-thread synchronization

requirements. Ecient use of memory is also important.

We present a novel, visually intuitive approach to partitioning two input sorted arrays

into pairs of contiguous sequences of elements, one from each array, such that 1) each pair

comprises any desired total number of elements, and 2) the elements of each pair form a

contiguous sequence in the output merged sorted array. While the resulting partition and the

computational complexity are similar to those of certain previous algorithms, our approach

is dierent, extremely intuitive, and oers interesting insights. Based on this, we present a

synchronization-free, cache-ecient merging (and sorting) algorithm.

While we use a shared memory architecture as the basis, our algorithm is easily adaptable

to additional architectures. In fact, our approach is even relevant to cache-ecient sequential

sorting. The algorithms are presented, along with important cache-related insights.

Merge Path – A Visually Intuitive Approach to Parallel Merging

Merge Path – Parallel Merging Made Simple