When can we sort in \(o(n\log n)\) time?

DOI10.1006/jcss.1997.1474zbMath0878.68059OpenAlexW1964765091MaRDI QIDQ1356890

Zvi Galil, Amir M. Ben-Amram

Publication date: 3 August 1997

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1997.1474

zbMATH Keywords

random access machine

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20)

Cites Work

• Unnamed Item
• Unnamed Item
• Upper bounds for sorting integers on random access machines
• Surpassing the information theoretic bound with fusion trees
• On the computational power of pushdown automata
• Organization and maintenance of large ordered indexes
• Hash functions for priority queues
• On parallel hashing and integer sorting
• On pointers versus addresses
• On the complexity of functions for random access machines

This page was built for publication: When can we sort in \(o(n\log n)\) time?