Lazy-Merge: A Novel Implementation for Indexed Parallel -Way In-Place Merging
Ahmad Salah, Kenli Li, Keqin Li · IEEE Transactions on Parallel and Distributed Systems · 2015
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(k log (n/k) + merge(n/p)), where k, n, and pare 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 O(log k), 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.