Parallelizing merge sort onto distributed memory parallel computers

Minsoo Jeon, Dongseung Kim

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)


Merge sort is useful in sorting a great number of data progressively, especially when they can be partitioned and easily collected to a few processors. Merge sort can be parallelized, however, conventional algorithms using distributed memory computers have poor performance due to the successive reduction of the number of participating processors by a half, up to one in the last merging stage. This paper presents load-balanced parallel merge sort where all processors do the merging throughout the computation. Data are evenly distributed to all processors, and every processor is forced to work in all merging phases. An analysis shows the upper bound of the speedup of the merge time as (P- 1)/log P where P is the number of processors. We have reached a speedup of 8.2 (upper bound is 10.5) on 32-processor Cray T3E in sorting of 4M 32-bit integers.

Original languageEnglish
Title of host publicationHigh Performance Computing - 4th International Symposium, ISHPC 2002, Proceedings
Number of pages10
Publication statusPublished - 2002
Event4th International Symposium on High Performance Computing, ISHPC 2002 - Kansai Science City, Japan
Duration: 2002 May 152002 May 17

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2327 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other4th International Symposium on High Performance Computing, ISHPC 2002
CityKansai Science City

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Parallelizing merge sort onto distributed memory parallel computers'. Together they form a unique fingerprint.

Cite this