Stable unmerging in linear time and constant space

DOI10.1016/0020-0190(87)90202-XzbMATH Open0653.68053MaRDI QIDQ1108017FDOQ1108017

Authors: Jeffrey S. Salowe, William Steiger 

Publication date: 1987

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

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

zbMATH Keywords

sorted listsspace-time complexity of unmerging

Mathematics Subject Classification ID

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

Cites Work

• Stable Sorting in Asymptotically Optimal Time and Extra Space
• Title not available (Why is that?)
• Stable Sorting and Merging with Optimal Space and Time Bounds

Cited In (10)

• 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
• Title not available (Why is that?)

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)