Adaptive sorting and the information theoretic lower bound

DOI10.1007/3-540-36494-3_57MaRDI QIDQ4418689zbMATH OpenFDO

Authors Amr Elmasry, Michael L. Fredman

Publication date 11 August 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2607/26070654.htm

Mathematics Subject Classification ID

Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Adaptive sorting: an information theoretic perspective
• On adaptive integer sorting
• Automata, Languages and Programming
• Experimental and Efficient Algorithms
• scientific article; zbMATH DE number 2163028

Cited in

(16)

• Efficient algorithms for the inverse sorting problem with bound constraints under the \(l_{\infty }\)-norm and the Hamming distance
• Inversions in \(k\)-sorted permutations
• Sorting shuffled monotone sequences
• Exploiting few inversions when sorting: Sequential and parallel algorithms
• Counting inversions adaptively
• Adaptive sorting: an information theoretic perspective
• scientific article; zbMATH DE number 437573 (Why is no real title available?)
• scientific article; zbMATH DE number 5568413 (Why is no real title available?)
• scientific article; zbMATH DE number 2163028 (Why is no real title available?)
• Priority queues, pairing, and adaptive sorting
• Optimally sorting evolving data
• Inversion-sensitive sorting algorithms in practice
• On adaptive integer sorting
• Experimental and Efficient Algorithms
• Automata, Languages and Programming
• Computing inversion pair cardinality through partition-based sorting

This page was built for publication: Adaptive sorting and the information theoretic lower bound

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