Deterministic sorting in O ( n log log n ) time and linear space

DOI10.1145/509907.509993MaRDI QIDQ3579249zbMATHOpenAlexFDO

Authors Yijie Han

Publication date 5 August 2010

Published in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/509907.509993

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10)

Cited in

(10)

• Compressed text indexing with wildcards
• Maximal common subsequence algorithms
• Efficient unbalanced merge-sort
• Lower bounds for external memory integer sorting via network coding
• New method in information processing for maintaining an efficient dynamic ordered set
• A new approach to all-pairs shortest paths on real-weighted graphs
• A survey on priority queues
• Order-preserving pattern matching with \(k\) mismatches
• A simple reduction from maximum weight matching to maximum cardinality matching
• The saga of minimum spanning trees

This page was built for publication: Deterministic sorting in O ( n log log n ) time and linear space

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