Upper bounds for sorting integers on random access machines

DOI10.1016/0304-3975(83)90023-3zbMath0533.68046OpenAlexW1985361644WikidataQ61051152 ScholiaQ61051152MaRDI QIDQ789897

Stefan Reisch, David G. 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)

Related Items (22)

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

Cites Work

• Preserving order in a forest in less than logarithmic time and linear space
• Time bounded random access machines
• On the computational power of pushdown automata
• Design and implementation of an efficient priority queue
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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