Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

On the improvement of the in-place merge algorithm parallelization

Bérenger Bramas 1, 2, * Quentin Bramas 1, 3
* Corresponding author
2 CAMUS - Compilation pour les Architectures MUlti-coeurS
Inria Nancy - Grand Est, ICube - Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie
Abstract : In this paper, we present several improvements in the parallelization of the in-place merge algorithm, which merges two contiguous sorted arrays into one with an O(T) space complexity (where T is the number of threads). The approach divides the two arrays into as many pairs of partitions as there are threads available; such that each thread can later merge a pair of partitions independently of the others. We extend the existing method by proposing a new algorithm to find the median of two partitions. Additionally, we provide a new strategy to divide the input arrays where we minimize the data movement, but at the cost of making this stage sequential. Finally, we provide the so-called linear shifting algorithm that swaps two partitions in-place with contiguous data access. We emphasize that our approach is straightforward to implement and that it can also be used for external (out of place) merging. The results demonstrate that it provides a significant speedup compared to sequential executions, when the size of the arrays is greater than a thousand elements.
Complete list of metadata
Contributor : Bérenger Bramas Connect in order to contact the contributor
Submitted on : Tuesday, May 26, 2020 - 10:51:39 AM
Last modification on : Thursday, December 2, 2021 - 3:16:48 AM


Files produced by the author(s)


  • HAL Id : hal-02613668, version 1
  • ARXIV : 2005.12648


Bérenger Bramas, Quentin Bramas. On the improvement of the in-place merge algorithm parallelization. 2020. ⟨hal-02613668⟩



Les métriques sont temporairement indisponibles