Parallel sorting algorithm using multiway merge and its implementation on a multi-mesh network

    Authors

    B. P. Sinha;A. Mukherjee

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    J. Parallel Distrib. Comput.

    Keywords

    multi-way merge; shear-sort; odd-even merge sort; 2D mesh; multi-mesh; multidimensional mesh; SIMD; MIMD; PRAM; EREW; CREW; Computer Science, Theory & Methods

    Abstract

    In this paper, we present a parallel sorting algorithm using the technique of multi-way merge. This algorithm, when implemented on a t dimensional mesh having n(t) nodes (t > 2), sorts n(t) elements in O((t(2) - 3t + 2) n) time, thus offering a better order of time complexity than the [((t(2) - t)n log n)/2 + O(nt)]- time algorithm of P, F. Corbett and I. D. Scherson (1992, IEEE Trans. Parallel Distrib. Systems 3, 626 632). Further, the proposed algorithm can also be implemented on a Multi-Mesh network (1999, D. Das, M. De, and B. P. Sinha. IEEE Trans. Comput. 48, 536-551) to sort N elements in 54N(1/4) + o(N-1/4) steps, which shows an improvement over 58N(1/4) + o(N-1/4) steps needed by the algorithm in (1997, M.De, D.Das: M.Ghosh, and P. B. Sinha. IEEE Trans. Comput. 46, 1132-1137). (C) 2000 Academic Press.

    Journal Title

    Journal of Parallel and Distributed Computing

    Volume

    60

    Issue/Number

    7

    Publication Date

    1-1-2000

    Document Type

    Article

    Language

    English

    First Page

    891

    Last Page

    907

    WOS Identifier

    WOS:000088124600005

    ISSN

    0743-7315

    Share

    COinS