Sorting and Searching in Multisets

DOI10.1137/0205001MaRDI QIDQ4088267zbMATH OpenOpenAlexFDO

Authors J. Ian Munro, P. M. Spira

Publication date 1976

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0205001

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Algorithms in computer science (68W99)

Cited in

(21)

• Probabilistic counting algorithms for data base applications
• Determining the mode
• Stable minimum space partitioning in linear time
• Sorting multisets stably in minimum space
• Finding modes with equality comparisons
• Linear-space data structures for range mode query in arrays
• Finding mode using equality comparisons
• From time to space: fast algorithms that yield small and fast data structures
• Array range queries
• Range Majority in Constant Time and Linear Space
• On compressing permutations and adaptive sorting
• Nearly-optimal mergesorts: fast, practical sorting methods that optimally adapt to existing runs
• Distribution-sensitive algorithms
• Sorting multisets stably in minimum space
• A general lower bound on the I/O-complexity of comparison-based algorithms
• Smooth heaps and a dual view of self-adjusting data structures
• Tight bounds for online stable sorting
• Galloping in fast-growth natural merge sorts
• Large alphabets and incompressibility
• Dynamic Shannon coding
• Sorting streamed multisets

This page was built for publication: Sorting and Searching in Multisets

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