Optimal merging and sorting on the EREW PRAM

DOI10.1016/0020-0190(89)90138-5zbMath0689.68085OpenAlexW2062679636MaRDI QIDQ582111

Christine Rüb, Torben Hagerup

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90138-5

zbMATH Keywords

parallel sortingEREW PRAMminimum-comparison merging and sortingparallel merging

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items

Fast integer merging on the EREW PRAM ⋮ An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram ⋮ Perfectly Load-Balanced, Stable, Synchronization-Free Parallel Merge ⋮ Improved parallel integer sorting without concurrent writing ⋮ Merging and sorting strings in parallel ⋮ Fast integer merging on the EREW PRAM ⋮ Integer merging on EREW PRAM ⋮ Fast randomized parallel methods for planar convex hull construction ⋮ Testing a simple polygon for monotonicity optimally in parallel ⋮ Parallel heap: an optimal parallel priority queue ⋮ Parallel merging with restriction ⋮ Parallel multiple search ⋮ Sorting in linear time? ⋮ OPTIMAL PARALLEL MATCHING ON BIPARTITE PERMUTATION GRAPHS ⋮ Space-efficient parallel merging ⋮ Finding the Convex Hull of Discs in Parallel ⋮ An optimal parallel algorithm for merging using multiselection

Cites Work

• Unnamed Item
• Sorting in \(c \log n\) parallel steps
• Parallel approximation algorithms for bin packing
• On Parallel Searching
• Deterministic coin tossing with applications to optimal parallel list ranking
• Parallel Merge Sort
• Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines
• Finding the maximum, merging, and sorting in a parallel computation model