Parallel Algorithms For Merging And Sorting

    Authors

    N. Deo;D. Sarkar

    Comments

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

    Abbreviated Journal Title

    Inf. Sci.

    Keywords

    COMPUTATION; Computer Science, Information Systems

    Abstract

    We present an O(log(min(m,n,j))-time sequential algorithm to select the jth-smallest element of an array resulting from the merging of two sorted arrays A and B of sizes m and n. This algorithm is then used to design two parallel algorithms to partition A and B into p subarrays of size O((m + n)/p) in O(N / p + log N) and O(N / p + log p log N) times on CREW PRAM AND EREW PRAM models with p processors, where N = m + n. A third parallel algorithm has been presented that partitions A and B in O(N / p + log p log N) time into p pairs of subarrays of size O(N / p) on EREW PRAM with p processors without using any selection algorithm. Finally, these partitioning algorithms are used to obtain optimal parallel merging and sorting algorithms on CREW PRAMS and EREW PRAMS.

    Journal Title

    Information Sciences

    Volume

    56

    Issue/Number

    1-3

    Publication Date

    1-1-1991

    Document Type

    Article

    Language

    English

    First Page

    151

    Last Page

    161

    WOS Identifier

    WOS:A1991FB55900009

    ISSN

    0020-0255

    Share

    COinS