Tight bounds for online stable sorting

DOI10.1016/J.JDA.2011.01.003zbMATH Open1221.68077OpenAlexW2081379545MaRDI QIDQ553955FDOQ553955

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

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

zbMATH Keywords

online algorithmsanalysis of algorithmssorting

Mathematics Subject Classification ID

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

Cites Work

• A Remark on Stirling's Formula
• Self-adjusting binary search trees
• Sorting and Searching in Multisets
• Title not available (Why is that?)
• Worst-Case Optimal Adaptive Prefix Coding
• How good is the information theory bound in sorting?
• Determining the mode
• Alphabetic Minimax Trees
• Title not available (Why is that?)
• A Best Possible Bound for The Weighted Path Length of Binary Search Trees
• Title not available (Why is that?)

Cited In (4)

• Worst-Case Optimal Adaptive Prefix Coding
• Efficient and compact representations of some non-canonical prefix-free codes
• Sorting streamed multisets
• 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)