Optimal Parallel Merging and Sorting Without Memory Conflicts
- 1 November 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-36 (11) , 1367-1369
- https://doi.org/10.1109/tc.1987.5009478
Abstract
A parallel algorithm is described for merging two sorted vectors of total length N. The algorithm runs on a shared-memory model of parallel computation that disallows more than one processor to simultaneously read from or write into the same memory location. It uses k processors where l ≤ k ≤ N and requires O(N/k + log k × log N) time. The proposed approach for merging leads to a parallel sorting algorithm that sorts a vector of length N in O(log 2 k + N/k) log N) time. Because they modify their behavior and hence their running time according to the number of available processors, the two new algorithms are said to be self-reconfiguring. In addition, both algorithms are optimal, for k ≤ N/log 2 N, in view of the Ω(N) and Ω(N log N) lower bounds on merging and sorting, respectively.Keywords
This publication has 8 references indexed in Scilit:
- Distributed SortingIEEE Transactions on Computers, 1985
- A taxonomy of parallel sortingACM Computing Surveys, 1984
- Optimal parallel algorithms for computing convex hulls and for sortingComputing, 1984
- Searching, Merging, and Sorting in Parallel ComputationIEEE Transactions on Computers, 1983
- Finding the median distributivelyJournal of Computer and System Sciences, 1982
- Routing, merging and sorting on parallel models of computationPublished by Association for Computing Machinery (ACM) ,1982
- Finding the maximum, merging, and sorting in a parallel computation modelJournal of Algorithms, 1981
- Parallelism in Comparison ProblemsSIAM Journal on Computing, 1975