Title

Parallel Algorithms For Merging And Sorting

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. © 1991.

Publication Date

1-1-1991

Publication Title

Information Sciences

Volume

56

Issue

1-3

Number of Pages

151-161

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/0020-0255(91)90028-S

Socpus ID

0026204033 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0026204033

This document is currently not available here.

Share

COinS