Title

Parallel Algorithms For Merging And Sorting

Authors

N Deo
D Sarkar

Title - Alternative

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.

Publication 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