Improved deterministic parallel integer sorting

DOI10.1016/0890-5401(91)90031-VzbMath0768.68023WikidataQ61051142 ScholiaQ61051142MaRDI QIDQ1175944

V. C. Prasad, P. C. P. Bhatt, Sanjeev Saxena, Torben Hagerup, Krzysztof Diks, Tomasz Radzik

Publication date: 25 June 1992

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

sorting algorithmCRCW PRAMlist ranking problemallocated PRAMdeterministic sorting of integers on a prallel RAMparallel recursive algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)

Related Items

An efficient parallel algorithm for the single function coarsest partition problem ⋮ Parallel integer sorting using small operations ⋮ \(O(\log \log n)\)-time integer geometry on the CRCW PRAM ⋮ Improved parallel integer sorting without concurrent writing ⋮ Sorting strings and constructing digital search trees in parallel ⋮ The complexity of parallel prefix problems on small domains ⋮ ERCW PRAMs and optical communication ⋮ Fast and optimal simulations between CRCW PRAMs ⋮ Merging and sorting strings in parallel ⋮ Conservative algorithms for parallel and sequential integer sorting ⋮ Improved nonconservative sequential and parallel integer sorting ⋮ An efficient parallel algorithm for building the separating tree ⋮ Approximating Huffman codes in parallel ⋮ The Fork95 programming language: Design, implementation, application. ⋮ Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees ⋮ Sorting on PRAMs with reconfigurable buses ⋮ Parallel algorithms for separable permutations ⋮ Optimal parallel suffix tree construction ⋮ A nearly optimal deterministic parallel Voronoi diagram algorithm ⋮ Sorting in linear time? ⋮ Parallel construction and query of index data structures for pattern matching on square matrices ⋮ Improved parallel construction of wavelet trees and rank/select structures ⋮ OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS ⋮ Improved fast integer sorting in linear space

Cites Work

• Optimal parallel algorithms on planar graphs
• Upper bounds for sorting integers on random access machines
• Towards optimal parallel bucket sorting
• Optimal parallel randomized algorithms for sparse addition and identification
• Simulations among concurrent-write PRAMs
• Axioms and hulls
• Faster optimal parallel prefix sums and list ranking
• Deterministic coin tossing with applications to optimal parallel list ranking
• Parallel Merge Sort
• Optimal bounds for decision problems on the CRCW PRAM
• Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
• Parallelism in random access machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item