Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge

2025/10/27 by Joshi, Amit
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2510.22882

Abstract

We present a merge-free algorithm for multi-way co-ranking, the problem of computing cut indices i₁,…,i_m that partition each of the m sorted sequences such that all prefix segments together contain exactly K elements. Our method extends two-list co-ranking to arbitrary m, maintaining per-sequence bounds that converge to a consistent global frontier without performing any multi-way merge or value-space search. Rather, we apply binary search to index-space. The algorithm runs in O(log(∑_t n_t) log m) time and O(m) space, independent of K. We prove correctness via an exchange argument and discuss applications to distributed fractional knapsack, parallel merge partitioning, and multi-stream joins. Keywords: Co-ranking \sep partitioning \sep Merge-free algorithms \sep Index-space optimization \sep Selection and merging \sep Data structures

Citations

• Simple in-place yet comparison-optimal Mergesort

Related

• Perfectly load-balanced, optimal, stable, parallel merge
• A note on self-improving sorting with hidden partitions
• On Slicing Sorted Integer Sequences
• Sorting and Ranking of Self-Delimiting Numbers with Applications to Outerplanar Graph Isomorphism
• Sorting Lists with Equal Keys Using Mergesort in Linear Time