Sorting multisets stably in minimum space

DOI10.1007/BF01178508zbMath0818.68066MaRDI QIDQ1338888

Jyrki Katajainen, Tomi A. Pasanen

Publication date: 23 November 1994

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

minimum space algorithmstable selectionstable unpartitioning

Mathematics Subject Classification ID

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

Related Items (4)

GENUS AND DIMENSION OF DIGITAL IMAGES AND THEIR TIME- AND SPACE-EFFICIENT COMPUTATION ⋮ Line-segment intersection made in-place ⋮ Space-efficient geometric divide-and-conquer algorithms ⋮ Selection from read-only memory with limited workspace

Cites Work

• Unnamed Item
• 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
• 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
• Splitsort -- an adaptive sorting algorithm
• Stable minimum space partitioning in linear time
• Sorting shuffled monotone sequences
• 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

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