Merge Path - Parallel Merging Made Simple

Citations Over TimeTop 10% of 2012 papers

Abstract

Merging two sorted arrays is a prominent building block for sorting and other functions. Its efficient parallelization requires balancing the load among compute cores, minimizing the extra work brought about by parallelization, and minimizing inter-thread synchronization requirements. Efficient use of memory is also important. We present a novel approach to partitioning the two 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 final merged sorted array. While the resulting partition and the computational complexity are similar to those of certain previous algorithms, our approach is different, extremely intuitive, and offers interesting insights. Based on this, we present a synchronization-free, cache-efficient merging (and sorting) algorithm. While we use CREW PRAM as the basis, our algorithm is easily adaptable to additional architectures. In fact, our approach is even relevant to sequential cache-efficient sorting. The algorithms and performance results are presented, along with important cache-related insights.

Related Papers

• → Array sort: an adaptive sorting algorithm on multi‐thread(2019)11 cited
• → Parallel merge sort with double merging(2014)10 cited
• → Distribution of Execution Times for Sorting Algorithms Implemented in Java(2015)2 cited
• Algorithms for external sorting(2015)
• → Performance Analysis of QuickMerge and QuickInsertionMerge Algorithms(2023)