Upper bounds for sorting integers on random access machines

DOI10.1016/0304-3975(83)90023-3zbMATH Open0533.68046OpenAlexW1985361644WikidataQ61051152 ScholiaQ61051152MaRDI QIDQ789897FDOQ789897

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

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\log n)\) time?

zbMATH Keywords

random access machinecomplexity of integer sorting

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Preserving order in a forest in less than logarithmic time and linear space
• On the computational power of pushdown automata
• Design and implementation of an efficient priority queue
• Time bounded random access machines
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (24)

• Improved deterministic parallel integer sorting
• Sorting real numbers in \(O(n \sqrt{\log n})\) time and linear space
• A Linear Time Algorithm for Ordered Partition
• On parallel integer sorting
• 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
• On Faster Integer Calculations Using Non-arithmetic Primitives
• Improved parallel integer sorting without concurrent writing
• 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\log n)\) time?
• Smoothing the Gap Between NP and ER
• Improved bounds for integer sorting in the EREW PRAM model
• Sorting Short Keys in Circuits of Size ${o(n \log n)}$
• Sorting and searching revisted

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)