Sorting multisets stably in minimum space

DOI10.1007/3-540-55706-7_37zbMath1502.68109OpenAlexW1591994087MaRDI QIDQ5056159

Jyrki Katajainen, Tomi A. Pasanen

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT '92 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55706-7_37

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (1)

Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
• Stable in situ sorting and minimum data movement
• A generalized, one-way, stackless quicksort
• Stable duplicate-key extraction with optimal time and space bounds
• Stable unmerging in linear time and constant space
• Sorting numbers in linear expected time and optimal extra space
• Stable minimum space partitioning in linear time
• Time bounds for selection
• Space-efficient parallel merging
• Quicksort for Equal Keys
• Simplified stable merging tasks
• Sorting and Searching in Multisets
• Stable Sorting in Asymptotically Optimal Time and Extra Space
• Sorting shuffled monotone sequences

This page was built for publication: Sorting multisets stably in minimum space