Tight bounds for online stable sorting

DOI10.1016/J.JDA.2011.01.003MaRDI QIDQ553955zbMATH OpenOpenAlexFDO

Authors Travis Gagie, Yakov Nekrich

Publication date 29 July 2011

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2011.01.003

zbMATH Keywords

online algorithmsanalysis of algorithmssorting

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Searching and sorting (68P10)

Recommendations

• Sorting stably, in place, with \(O(n \log n)\) comparisons and \(O(n)\) moves
• Sorting streamed multisets
• STACS 2005
• Sorting multisets stably in minimum space
• Stable in situ sorting and minimum data movement

Cites work

• scientific article; zbMATH DE number 4009819 (Why is no real title available?)
• scientific article; zbMATH DE number 177571 (Why is no real title available?)
• scientific article; zbMATH DE number 3802822 (Why is no real title available?)
• A Best Possible Bound for The Weighted Path Length of Binary Search Trees
• A Remark on Stirling's Formula
• Alphabetic Minimax Trees
• Determining the mode
• How good is the information theory bound in sorting?
• Self-adjusting binary search trees
• Sorting and Searching in Multisets
• Worst-Case Optimal Adaptive Prefix Coding

Cited in

(4)

• Worst-Case Optimal Adaptive Prefix Coding
• Sorting streamed multisets
• Efficient and compact representations of some non-canonical prefix-free codes
• On-line sorting of twisted sequences in linear time

This page was built for publication: Tight bounds for online stable sorting

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