Sorting in linear time?
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 1263219
- Sorting in linear expected time
- On the time-space tradeoff for sorting with linear queries
- Deterministic sorting in O(nloglogn) time and linear space
- Sorting, linear time and the satisfiability problem
- scientific article; zbMATH DE number 1629826
- Sorting numbers in linear expected time and optimal extra space
Cites work
- A guided tour of Chernoff bounds
- A Reliable Randomized Algorithm for the Closest-Pair Problem
- Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines
- An Efficient Parallel Biconnectivity Algorithm
- Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
- Deterministic coin tossing with applications to optimal parallel list ranking
- Expected time bounds for selection
- Explicit constructions of linear-sized superconcentrators
- scientific article; zbMATH DE number 4064468 (Why is no real title available?)
- scientific article; zbMATH DE number 3757704 (Why is no real title available?)
- scientific article; zbMATH DE number 52113 (Why is no real title available?)
- scientific article; zbMATH DE number 1303597 (Why is no real title available?)
- scientific article; zbMATH DE number 1142304 (Why is no real title available?)
- scientific article; zbMATH DE number 767429 (Why is no real title available?)
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- Improved deterministic parallel integer sorting
- Improved nonconservative sequential and parallel integer sorting
- Improved parallel integer sorting without concurrent writing
- Optimal bounds for decision problems on the CRCW PRAM
- Optimal merging and sorting on the EREW PRAM
- Optimal parallel string algorithms: sorting, merging and computing the minimum
- Parallel Merge Sort
- Priority queues: small, monotone and trans-dichotomous
- Searching, Merging, and Sorting in Parallel Computation
- Simulations among concurrent-write PRAMs
- Sorting in \(c \log n\) parallel steps
- Surpassing the information theoretic bound with fusion trees
- Three Partition Refinement Algorithms
- Universal classes of hash functions
- Upper bounds for sorting integers on random access machines
Cited in
(34)- Notes on the complexity of sorting in abstract machines
- Hybridsort revisited and parallelized
- Sorting numbers in linear expected time and optimal extra space
- When can we sort in o(n n) time?
- Sorting real numbers in \(O(n \sqrt{\log n})\) time and linear space
- Construct a perfect word hash function in time independent of the size of integers
- Expected linear time sorting for word size \(\Omega (\log ^{2} n \log\log n)\)
- Linear-time approximation for maximum weight matching
- A Linear Time Algorithm for Ordered Partition
- Faster Fully-Dynamic Minimum Spanning Forest
- Radix Sorting with No Extra Space
- scientific article; zbMATH DE number 4090816 (Why is no real title available?)
- Sorting in Average Time o(\log \,n)
- scientific article; zbMATH DE number 1263219 (Why is no real title available?)
- scientific article; zbMATH DE number 2079401 (Why is no real title available?)
- 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
- Deterministic sorting in O(nloglogn) time and linear space
- Group testing: revisiting the ideas
- Sorting short integers: the exposition
- Sorting Short Keys in Circuits of Size ${o(n \log n)}$
- Dynamic ordered sets with approximate queries, approximate heaps and soft heaps
- Generic top-down discrimination for sorting and partitioning in linear time
- Algorithms – ESA 2004
- Computational Science – ICCS 2005
- Substring complexities on run-length compressed strings
- Predecessor on the Ultra-Wide Word RAM
- Faster approximate string matching for short patterns
- Linear time runs over general ordered alphabets
- Sorting short integers
- Upper bounds for sorting integers on random access machines
- Improved nonconservative sequential and parallel integer sorting
- Well-separated pair decomposition in linear time?
- An optimal maximal independent set algorithm for bounded-independence graphs
This page was built for publication: Sorting in linear time?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1273863)
