Stable unmerging in linear time and constant space

DOI10.1016/0020-0190(87)90202-XMaRDI QIDQ1108017zbMATH OpenFDO

Authors Jeffrey S. Salowe, William Steiger

Publication date 1987

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

sorted listsspace-time complexity of unmerging

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Recommendations

• Stable Linear Time Sublinear Space Merging
• Unstable linear time O(1) space merging
• A practically efficient and almost linear unification algorithm
• Asymptotically efficient in-place merging
• Asymptotically efficient in-place merging
• Stable minimum space partitioning in linear time
• Sublinear merging and natural mergesort
• Time-space optimal parallel merging and sorting
• Disjoint stable matchings in linear time
• Strategies for stable merge sorting

Cites work

• scientific article; zbMATH DE number 3374945 (Why is no real title available?)
• Stable Sorting and Merging with Optimal Space and Time Bounds
• Stable Sorting in Asymptotically Optimal Time and Extra Space

Cited in

(10)

• scientific article; zbMATH DE number 1437310 (Why is no real title available?)
• Stable duplicate-key extraction with optimal time and space bounds
• An in-place algorithm for Klee's measure problem in two dimensions
• In-place algorithms for computing (Layers of) maxima
• Selecting distances in the plane
• Stable in situ sorting and minimum data movement
• Stable minimum space partitioning in linear time
• Line-segment intersection made in-place
• Sorting multisets stably in minimum space
• Sorting multisets stably in minimum space

This page was built for publication: Stable unmerging in linear time and constant space

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