A Time-space Efficient Algorithm for Parallel k-way In-place Merging based on Sequence Partitioning and Perfect Shuffle

The huge data volumes, big data, and the emergence of new parallel architectures lead to revisiting classic computer science topics. The motivation of the proposed work for revisiting the parallel k-way in-place merging is primarily related to the unsuitability of the current state-of-the-art parallel algorithms for multicore CPUs with shared memory. These architectures can be profitably employed to solve this problem in parallel. Recently, Intel introduced the parallel Standard Template Library (STL) implementation for multicore CPUs, but it has no in-place merge function with the in-place property. We propose Partition-Shuffle-merge (PS-merge) to address this problem. PS-merge includes combining sequence partitioning with the in-place perfect shuffle effect to address the k-way merge task. At first, each sequence is divided into t equal-sized partitions or ranges. Thus, each partition is spread over at most k sequences. Then, perfect shuffle is utilized as a replacement for the classic block rearrangement. Finally, range subpartitions are merged using a sequential in-place merging algorithm. To evaluate the proposed algorithm, as PS-merge produces the standard merging format, we compare this algorithm against the state-of-the-art methods, bitonic merge, a parallel binary merge tree, and lazy-merge. PS-merge shows a significant improvement in overall execution time.