Sorting in linear time?
From MaRDI portal
Publication:1273863
DOI10.1006/jcss.1998.1580zbMath0920.68044OpenAlexW1984816083WikidataQ61051134 ScholiaQ61051134MaRDI QIDQ1273863
Publication date: 6 January 1999
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1998.1580
Related Items (14)
A Linear Time Algorithm for Ordered Partition ⋮ Faster Fully-Dynamic Minimum Spanning Forest ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ Sorting Short Keys in Circuits of Size ${o(n \log n)}$ ⋮ Construct a perfect word hash function in time independent of the size of integers ⋮ Substring complexities on run-length compressed strings ⋮ Worst-case efficient single and multiple string matching on packed texts in the word-RAM model ⋮ Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism ⋮ Generic top-down discrimination for sorting and partitioning in linear time ⋮ Faster approximate string matching for short patterns ⋮ Well-separated pair decomposition in linear time? ⋮ Unnamed Item ⋮ An optimal maximal independent set algorithm for bounded-independence graphs ⋮ Group testing: Revisiting the ideas
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal merging and sorting on the EREW PRAM
- Upper bounds for sorting integers on random access machines
- A guided tour of Chernoff bounds
- Improved nonconservative sequential and parallel integer sorting
- Sorting in \(c \log n\) parallel steps
- Simulations among concurrent-write PRAMs
- Explicit constructions of linear-sized superconcentrators
- Improved deterministic parallel integer sorting
- Universal classes of hash functions
- Surpassing the information theoretic bound with fusion trees
- Improved parallel integer sorting without concurrent writing
- Optimal parallel string algorithms
- Searching, Merging, and Sorting in Parallel Computation
- An Efficient Parallel Biconnectivity Algorithm
- Deterministic coin tossing with applications to optimal parallel list ranking
- Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
- Parallel Merge Sort
- Three Partition Refinement Algorithms
- Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines
- Expected time bounds for selection
- A Reliable Randomized Algorithm for the Closest-Pair Problem
- Priority queues: Small, monotone and trans-dichotomous
- Optimal bounds for decision problems on the CRCW PRAM
This page was built for publication: Sorting in linear time?
