Lazy-Merge: A Novel Implementation for Indexed Parallel $K$ -Way In-Place Merging

摘要

Merging sorted segments is a core topic of fundamental computer science that has many different applications, such as $n$ -body simulation. In this research, we propose Lazy-Merge, a novel implementation of sequential in-place $k$ -way merging algorithms, that can be utilized in their parallel counterparts. The implementation divides the $k$ -way merging problem into $t$ ordered and independent smaller $k$ -way merging tasks (partitions), but each merging task includes a set of scattered ranges to be merged by an existing merging algorithm. The final merged list includes ranges with ordered elements, but the ranges themselves are not ordered. Lazy-Merge utilizes a novel usage of indexes to access the entire set of merged elements in order. Its merging time complexity is $O(klog (n/k)+merge(n/p))$ , where $k$ , $n$ , and $p$ are the number of segments, the list size and the number of processors (partitions), respectively. Here, $merge(n/p)$ represents the time needed to merge $n/p$ elements by the used in-place merging algorithm. The time complexity of accessing an element in the merged list is $Oleft(log kright)$ , that time can be constant if $k$ processors are used. The results of the proposed work are compared with those of bitonic merge and the best time-space optimal algorithms on number of moves and execution time. In comparison with the existing algorithms, significant speedup and reasonable reduction factor for number of moves have been achieved.