Searching, Merging, and Sorting in Parallel Computation

DOI10.1109/TC.1983.1676138zbMath0525.68039MaRDI QIDQ3038630

Clyde P. Kruskal

Publication date: 1983

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

zbMATH Keywords

sortingparallel computationsearchingmergingcomparison problemsnumber of comparison steps

Mathematics Subject Classification ID

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

Related Items (33)

Routing, merging, and sorting on parallel models of computation ⋮ Fast integer merging on the EREW PRAM ⋮ Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications ⋮ Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs ⋮ Polynomial terse sets ⋮ Parallel construction of a suffix tree with applications ⋮ Improved parallel integer sorting without concurrent writing ⋮ Sweep methods for parallel computational geometry ⋮ Sorting strings and constructing digital search trees in parallel ⋮ Merging and sorting strings in parallel ⋮ Fast integer merging on the EREW PRAM ⋮ A complexity theory of efficient parallel algorithms ⋮ Parallel selection ⋮ Integer merging on EREW PRAM ⋮ Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm ⋮ On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case ⋮ Fast sequential and parallel algorithms for finding extremal sets ⋮ Parallel priority queues ⋮ Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs ⋮ Heaps with bits ⋮ Line-segment intersection reporting in parallel ⋮ Constructing arrangements optimally in parallel ⋮ Parallel merging with restriction ⋮ Parallel computation of the Burrows Wheeler transform in compact space ⋮ An efficient parallel algorithm for finding minimum weight matching for points on a convex polygon ⋮ Parallel algorithms for merging and sorting ⋮ A nearly optimal deterministic parallel Voronoi diagram algorithm ⋮ Sorting in linear time? ⋮ On the complexity of finding the chromatic number of a recursive graph. I: The bounded case ⋮ Parallel comparison merging of many-ordered lists ⋮ A model of sequential computation with Pipelined access to memory ⋮ Space-efficient parallel merging ⋮ Parallel comparison algorithms for approximation problems

This page was built for publication: Searching, Merging, and Sorting in Parallel Computation