Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms

DOI10.1137/0218041zbMath0679.68091OpenAlexW2023518480WikidataQ61772707 ScholiaQ61772707MaRDI QIDQ4729356

John H. Reif, Sanguthevar Rajasekaran

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/4cc4c340e309cd50fcdd6715d9e77e39de353683

zbMATH Keywords

radix sortoptimal algorithmsrandom permutationsprefix sumparallel RAMrandomized parallel sorting algorithms

Mathematics Subject Classification ID

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

Related Items (26)

Fast integer merging on the EREW PRAM ⋮ Optimal parallel algorithms for multiple updates of minimum spanning trees ⋮ An optimal parallel algorithm for sorting multisets ⋮ Parallel integer sorting using small operations ⋮ A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon ⋮ The parallel complexity of integer prefix summation ⋮ Probabilistic integer sorting ⋮ Improved parallel integer sorting without concurrent writing ⋮ SORTING AND SELECTION ON DISTRIBUTED MEMORY BUS COMPUTERS ⋮ A randomized sorting algorithm on the BSP model ⋮ ERCW PRAMs and optical communication ⋮ Parallel Weighted Random Sampling ⋮ Conservative algorithms for parallel and sequential integer sorting ⋮ Fast integer merging on the EREW PRAM ⋮ Improved deterministic parallel integer sorting ⋮ Optimal parallel algorithms for forest and term matching ⋮ Parallel interval order recognition and construction of interval representations ⋮ Dynamic point location in arrangements of hyperplanes ⋮ RANDOMIZED SORTING ON THE POPS NETWORK ⋮ Delayed path coupling and generating random permutations ⋮ More Efficient Parallel Integer Sorting ⋮ A nearly parallel algorithm for the Voronoi diagram of a convex polygon ⋮ Improved parallel construction of wavelet trees and rank/select structures ⋮ Improved fast integer sorting in linear space ⋮ On parallel integer sorting ⋮ Deterministic parallel list ranking

Uses Software

• Algorithm 447

This page was built for publication: Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms