Parallel Merge Sort
From MaRDI portal
Publication:3796769
DOI10.1137/0217049zbMath0651.68077OpenAlexW1978583881WikidataQ56057496 ScholiaQ56057496MaRDI QIDQ3796769
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0217049
Related Items
Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs ⋮ Finding the k shortest paths in parallel ⋮ Constrained square-center problems ⋮ PRAM's towards realistic parallelism: BRAM's ⋮ Retrieval of scattered information by EREW, CREW and CRCW PRAMs ⋮ Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree ⋮ The (1|1)-Centroid Problem in the Plane with Distance Constraints ⋮ On the planar piecewise quadratic 1-center problem ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Parallel construction of quadtrees and quality triangulations ⋮ Probabilistic integer sorting ⋮ OPTIMAL PARALLEL PREPROCESSING ALGORITHMS FOR TESTING WEAK VISIBILITY OF POLYGONS FROM SEGMENTS ⋮ AN EFFICIENT ALGORITHM FOR MANAGING A PARALLEL HEAP∗ ⋮ SCHEDULING INTERVAL ORDERS IN PARALLEL ⋮ SORTING AND SELECTION ON DISTRIBUTED MEMORY BUS COMPUTERS ⋮ o(log4 n) time parallel maximal matching algorithm using linear number of processors ⋮ A note on the 1-maximal elements problem ⋮ A randomized sorting algorithm on the BSP model ⋮ Efficient parallel graph algorithms for coarse grained multicomputers and BSP ⋮ Fast sequential and parallel algorithms for finding the largest rectangle separating two sets ⋮ On parallel complexity of maximum f-matching and the degree sequence problem ⋮ A centroid labelling technique and its application to path selection in trees ⋮ Parallel Weighted Random Sampling ⋮ Property Suffix Array with Applications in Indexing Weighted Sequences ⋮ Self-simulation for the Passive Optical Star model ⋮ A compact data structure and parallel algorithms for permutation graphs ⋮ Controlling the spread of infectious diseases by using random walk method to remove many important links ⋮ Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph ⋮ Fast integer merging on the EREW PRAM ⋮ Nearly Work-Efficient Parallel Algorithm for Digraph Reachability ⋮ Fast sequential and parallel algorithms for finding extremal sets ⋮ Learning nested concept classes with limited storage ⋮ ON COST-OPTIMAL MERGE OF TWO INTRANSITIVE SORTED SEQUENCES ⋮ Optimal shooting: Characterizations and applications ⋮ Computing with Spikes: The Advantage of Fine-Grained Timing ⋮ THE ONION DIAGRAM: A VORONOI-LIKE TESSELLATION OF A PLANAR LINE SPACE AND ITS APPLICATIONS ⋮ Two-variable linear programming in parallel ⋮ EFFICIENT PARALLEL RANGE SEARCHING AND PARTITIONING ALGORITHMS* ⋮ Optimal parallel suffix tree construction ⋮ PARALLEL CONSTRUCTION OF QUADTREES AND QUALITY TRIANGULATIONS ⋮ Fast parallel algorithms for the maximum empty rectangle problem. ⋮ Parallel algorithms for red--black trees ⋮ Two-variable linear programming in parallel ⋮ Fast and compact planar embeddings ⋮ Fragile complexity of comparison-based algorithms ⋮ Minimizing Distance-to-Sight in Polygonal Domains ⋮ A Pictorial Description of Cole’s Parallel Merge Sort ⋮ Computing a geodesic two-center of points in a simple polygon ⋮ Efficient parallel algorithm to compute a doubly perfect elimination ordering of a doubly chordal graph ⋮ Space-efficient parallel merging ⋮ ON THE POWER OF SOME PRAM MODELS ⋮ A theorem on permutation graphs with applications ⋮ The geodesic 2-center problem in a simple polygon ⋮ An efficient parallel algorithm for the single function coarsest partition problem ⋮ A note on parallel complexity of maximum \(f\)-matching ⋮ An optimal parallel algorithm for sorting multisets ⋮ Parallel integer sorting using small operations ⋮ Optimal edge ranking of trees in polynomial time ⋮ A time-optimal parallel algorithm for three-dimensional convex hulls ⋮ Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM ⋮ An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem ⋮ Retrieval of scattered information by EREW, CREW, and CRCW PRAMs ⋮ Improved parallel integer sorting without concurrent writing ⋮ Efficient piecewise-linear function approximation using the uniform metric ⋮ Sweep methods for parallel computational geometry ⋮ Parallel construction of binary trees with near optimal weighted path length ⋮ Sorting strings and constructing digital search trees in parallel ⋮ Exploiting few inversions when sorting: Sequential and parallel algorithms ⋮ The interval-merging problem ⋮ The maximin line problem with regional demand ⋮ Parametric search made practical ⋮ A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms ⋮ An optimal parallel algorithm for the minimum circle-cover problem ⋮ The queue-read queue-write asynchronous PRAM model ⋮ Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems ⋮ Planar stage graphs: Characterizations and applications ⋮ Parallel \(N\)-free order recognition ⋮ An improved reliability bound of a probabilistic parallel integer sorting algorithm ⋮ Sorting roughly sorted sequences in parallel ⋮ Efficient parallel k selection algorithm ⋮ Communication complexity of PRAMs ⋮ A complexity theory of efficient parallel algorithms ⋮ Parallel algorithms for the segment dragging problem ⋮ An efficient parallel algorithm for scheduling interval ordered tasks ⋮ Cost-sensitive active learning with a label uniform distribution model ⋮ Improved deterministic parallel integer sorting ⋮ An optimal parallel adaptive sorting algorithm ⋮ Parallel priority queues ⋮ Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs ⋮ Parallel and serial heuristics for the minimum set cover problem ⋮ Optimal parallel algorithms for point-set and polygon problems ⋮ Efficient parallel algorithms for doubly convex-bipartite graphs ⋮ A simple randomized parallel algorithm for maximal f-matchings ⋮ Parallel interval order recognition and construction of interval representations ⋮ Parallel rectilinear shortest paths with rectangular obstacles ⋮ Geometric pattern matching under Euclidean motion ⋮ Line-segment intersection reporting in parallel ⋮ A new graph triconnectivity algorithm and its parallelization ⋮ Engineering parallel string sorting ⋮ An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model ⋮ Parallel time and space upper-bounds for the subset-sum problem ⋮ Optimal parallel time bounds for the maximum clique problem on intervals ⋮ Optimal parallel algorithms for finding cut vertices and bridges of interval graphs ⋮ A simple parallel algorithm for computing the diameters of all vertices in a tree and its application ⋮ On similarity of polynomial configurations ⋮ An elegant algorithm for the construction of suffix arrays ⋮ Testing a simple polygon for monotonicity optimally in parallel ⋮ Efficient parallel term matching and anti-unification ⋮ A parallel algorithm to construct a dominance graph on nonoverlapping rectangles ⋮ Parallel search algorithms for graphs and trees ⋮ Constructing the Voronoi diagram of a set of line segments in parallel ⋮ On single-walk parallelization of the job shop problem solving algorithms ⋮ Matching parentheses in parallel ⋮ Parallel algorithms for separable permutations ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ Parallel heap: an optimal parallel priority queue ⋮ Computing the center region and its variants ⋮ Dominance made simple ⋮ Finding the upper envelope of n line segments in O(n log n) time ⋮ Optimal merging and sorting on the EREW PRAM ⋮ A note on adaptive parallel sorting ⋮ A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs ⋮ Constructing arrangements optimally in parallel ⋮ Optimal parallel algorithms on circular-arc graphs ⋮ Parallel multiple search ⋮ Optimal parallel quicksort on EREW PRAM ⋮ Approximate algorithms for the Knapsack problem on parallel computers ⋮ Sorting in linear time? ⋮ More general parallel tree contraction: Register allocation and broadcasting in a tree ⋮ Modifying edges of a network to obtain short subgraphs ⋮ On the complexity of the k-chain subgraph cover problem ⋮ A parallel circle-cover minimization algorithm ⋮ Computing Prüfer codes efficiently in parallel ⋮ VPSPACE and a transfer theorem over the complex field ⋮ Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time ⋮ Parallel construction and query of index data structures for pattern matching on square matrices ⋮ Assigning weights to minimize the covering radius in the plane ⋮ An adaptive algorithm for maximization of non-submodular function with a matroid constraint ⋮ Parallel preprocessing for path queries without concurrent reading. ⋮ Removing randomness in parallel computation without a processor penalty ⋮ A simple optimal parallel algorithm for the minimum coloring problem on interval graphs ⋮ On parallel rectilinear obstacle-avoiding paths ⋮ On parallel integer sorting ⋮ Improving the efficiency of parallel minimum spanning tree algorithms ⋮ Parallel comparison merging of many-ordered lists ⋮ Parallel solutions to geometric problems in the scan model of computation ⋮ Recognition algorithm for intersection graphs of edge disjoint paths in a tree ⋮ Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space ⋮ Selecting small ranks in EREW PRAM ⋮ A parallel algorithm for approximate regularity. ⋮ An optimal parallel algorithm for merging using multiselection
