Asymptotically efficient in-place merging

DOI10.1016/S0304-3975(98)00162-5MaRDI QIDQ5915346zbMATH OpenDBLPWikidataFDO

Authors Viliam Geffert, Jyrki Katajainen, Tomi A. Pasanen

Publication date 4 June 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(98)00162-5

zbMATH Keywords

in-place algorithmsmergingsorting

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Recommendations

• Asymptotically efficient in-place merging
• SOFSEM 2006: Theory and Practice of Computer Science
• scientific article; zbMATH DE number 4001497
• Optimizing stable in-place merging.
• Multiway In-Place Merging

Cites work

• A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 4001497 (Why is no real title available?)
• scientific article; zbMATH DE number 3374945 (Why is no real title available?)
• On a stable minimum storage merging algorithm
• On the Optimality of Linear Merge
• Selection from read-only memory and sorting with minimum data movement
• Simplified stable merging tasks
• Sorting with minimum data movement
• Stable Sorting and Merging with Optimal Space and Time Bounds

Cited in

(23)

• Stable unmerging in linear time and constant space
• Optimizing stable in-place merging.
• QuickXsort: a fast sorting scheme in theory and practice
• Line-segment intersection made in-place
• Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
• Efficient unbalanced merge-sort
• Context-free languages can be accepted with absolutely no space overhead
• Multiway In-Place Merging
• Perfectly load-balanced, stable, synchronization-free parallel merge
• Ratio Based Stable In-Place Merging
• Stable Linear Time Sublinear Space Merging
• Unstable linear time O(1) space merging
• scientific article; zbMATH DE number 4001497 (Why is no real title available?)
• The analysis of a simple in-place merging algorithm
• scientific article; zbMATH DE number 1437310 (Why is no real title available?)
• GENUS AND DIMENSION OF DIGITAL IMAGES AND THEIR TIME- AND SPACE-EFFICIENT COMPUTATION
• SOFSEM 2006: Theory and Practice of Computer Science
• Asymptotically efficient in-place merging
• A simple algorithm for in-place merging
• An in-place algorithm for Klee's measure problem in two dimensions
• In-place algorithms for computing (Layers of) maxima
• Space-efficient geometric divide-and-conquer algorithms
• Multiway in-place merging

This page was built for publication: Asymptotically efficient in-place merging

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