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    $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     $O\left(\log k\right)$       , 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.
['Ahmad Salah', 'Kenli Li', 'Keqin Li']
Lazy-Merge: A Novel Implementation for Indexed Parallel $K$ -Way In-Place Merging