Tight bounds for online stable sorting

DOI10.1016/j.jda.2011.01.003zbMath1221.68077OpenAlexW2081379545MaRDI QIDQ553955

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

sortingonline algorithmsanalysis of algorithms

Mathematics Subject Classification ID

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

Related Items (2)

Worst-Case Optimal Adaptive Prefix Coding ⋮ Efficient and compact representations of some non-canonical prefix-free codes

Cites Work

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

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