Upper bounds for sorting integers on random access machines

DOI10.1016/0304-3975(83)90023-3MaRDI QIDQ789897zbMATH OpenOpenAlexWikidataFDO

Authors Stefan Reisch, David Kirkpatrick

Publication date 1984

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(83)90023-3

zbMATH Keywords

random access machinecomplexity of integer sorting

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1263219
• Sorting in linear time?
• scientific article; zbMATH DE number 742994
• Improved parallel integer sorting without concurrent writing
• When can we sort in o(n n) time?

Cites work

• scientific article; zbMATH DE number 3846871 (Why is no real title available?)
• scientific article; zbMATH DE number 3653573 (Why is no real title available?)
• scientific article; zbMATH DE number 3757704 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• Design and implementation of an efficient priority queue
• On the computational power of pushdown automata
• Preserving order in a forest in less than logarithmic time and linear space
• Time bounded random access machines

Cited in

(24)

• Sorting and searching revisted
• Improved deterministic parallel integer sorting
• Sorting real numbers in \(O(n \sqrt{\log n})\) time and linear space
• On parallel integer sorting
• A Linear Time Algorithm for Ordered Partition
• Fast geometric approximation techniques and geometric embedding problems
• Improved fast integer sorting in linear space
• Notes on the complexity of sorting in abstract machines
• Parallel construction of binary trees with near optimal weighted path length
• Improved parallel integer sorting without concurrent writing
• On Faster Integer Calculations Using Non-arithmetic Primitives
• Sorting short integers: the exposition
• Constant-time sorting
• Scanline algorithms on a grid
• Algorithms for dense graphs and networks on the random access computer
• Conservative algorithms for parallel and sequential integer sorting
• Sorting in linear time?
• Improved nonconservative sequential and parallel integer sorting
• Greedy matching on a grid
• P-RAM vs. RP-RAM
• When can we sort in o(n n) time?
• Improved bounds for integer sorting in the EREW PRAM model
• Smoothing the Gap Between NP and ER
• Sorting Short Keys in Circuits of Size ${o(n \log n)}$

This page was built for publication: Upper bounds for sorting integers on random access machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q789897)