Stable in situ sorting and minimum data movement

DOI10.1007/BF02017344MaRDI QIDQ911311zbMATH OpenOpenAlexFDO

Authors J. Ian Munro, Venkatesh Raman, Jeffrey S. Salowe

Publication date 1990

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02017344

zbMATH Keywords

minimum data movementstable in situ sorting

Mathematics Subject Classification ID

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

Recommendations

• Sorting with minimum data movement
• scientific article; zbMATH DE number 140497
• Fast stable in-place sorting with \(O(n)\) data moves
• In-place sorting with fewer moves
• Selection from read-only memory and sorting with minimum data movement
• STACS 2005
• In-place sorting
• Sorting multisets stably in minimum space
• Sorting multisets stably in minimum space
• Automata, Languages and Programming

Cites work

• scientific article; zbMATH DE number 140497 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3633709 (Why is no real title available?)
• scientific article; zbMATH DE number 4003539 (Why is no real title available?)
• scientific article; zbMATH DE number 3374945 (Why is no real title available?)
• scientific article; zbMATH DE number 3405492 (Why is no real title available?)
• A generalized, one-way, stackless quicksort
• Simplified stable merging tasks
• Stable Sorting and Merging with Optimal Space and Time Bounds
• Stable unmerging in linear time and constant space
• Transposing Matrices in a Digital Computer

Cited in

(18)

• In-place linear probing sort
• scientific article; zbMATH DE number 140497 (Why is no real title available?)
• Stable minimum space partitioning in linear time
• Quicksort for Equal Keys
• An algorithm of two-way passed and stably quick sort (TPQA)
• Sorting multisets stably in minimum space
• Tight bounds for online stable sorting
• Space-efficient planar convex hull algorithms
• STACS 2005
• In-place sorting with fewer moves
• Sorting multisets stably in minimum space
• What is a sorting function?
• Stable duplicate-key extraction with optimal time and space bounds
• Fast stable in-place sorting with \(O(n)\) data moves
• Selection from read-only memory and sorting with minimum data movement
• Sorting stably, in place, with \(O(n \log n)\) comparisons and \(O(n)\) moves
• Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
• Sorting with minimum data movement

Describes a project that uses

Uses Software

• Quicksort

This page was built for publication: Stable in situ sorting and minimum data movement

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