Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation

Parallel Merge Sort for Distributed Memory Architectures

Abstract : Cole presented a parallel merge sort for the PRAM model that performs in log n parallel steps using n processors. He gave an algorithm for the CREW PRAM model for which the constant in the running time is small. He also gave a more complex version of the algorithm for the EREW PRAM; the constant factor in the running time is still moderate but not as small. In this paper we give an approach to implement Cole's parallel merge sort on a distributed memory architecture. Both, the CREW and the EREW algorithms have been considered. A data placement algorithm is presented as well as the associated data movements. Our proposition sorts n items using exactly n processors in log n parallel time. The constant in the running time is only one greater than the one obtained for the PRAM model.
Document type :
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:10:31 AM
Last modification on : Saturday, September 11, 2021 - 3:18:55 AM


Files produced by the author(s)


  • HAL Id : hal-02101948, version 1



Jean-Marc Adamo, Luis Trejo. Parallel Merge Sort for Distributed Memory Architectures. [Research Report] LIP RR-1994-05, Laboratoire de l'informatique du parallélisme. 1994, 2+35p. ⟨hal-02101948⟩



Record views


Files downloads