Parallel Merge Sort with Load Balancing

Minsoo Jeon, Dongseung Kim

    Research output: Contribution to journalArticlepeer-review

    22 Citations (Scopus)

    Abstract

    Parallel merge sort is useful for sorting a large quantity of data progressively. The merge sort should be parallelized carefully since the conventional algorithm has poor performance due to the successive reduction of the number of participating processors by half, and down to one in the last merging stage. The proposed load-balanced merge sort utilizes all processors throughout the computation. It evenly distributes data to all processors in each stage. Thus every processor is forced to work in all phases. Significant performance enhancement has been achieved up to a speedup of (P-1)/log P where P is the number of processors. Experimental results demonstrate a speedup of 9. 6 (upper bound of 10.7) on 32-processor Cray T3E when sorting 4M 32-bit integers, and a speed up of 2.3 (upper bound of 2.8) on an 8-node PC cluster.

    Original languageEnglish
    Pages (from-to)21-33
    Number of pages13
    JournalInternational Journal of Parallel Programming
    Volume31
    Issue number1
    DOIs
    Publication statusPublished - 2003 Feb

    Bibliographical note

    Funding Information:
    This research was supported by KOSEF Grant (No. R01-2001-00341).

    Keywords

    • Load balancing
    • Merge sort
    • Parallel algorithm
    • Splitter

    ASJC Scopus subject areas

    • Software
    • Theoretical Computer Science
    • Information Systems

    Fingerprint

    Dive into the research topics of 'Parallel Merge Sort with Load Balancing'. Together they form a unique fingerprint.

    Cite this