Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge Journal: Information Processing Letters
Amit Joshi [email protected] [email protected] · 2025
Read Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge Journal: Information Processing Letters by Amit Joshi [email protected] [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-22882.txt.
Introduction
Splitting many sorted lists at a shared rank is a core task. Amit Joshi, writing alone in 2025, gives a merge free method for it. The task is multi way co-ranking. Cut indices must make all prefix segments hold exactly K elements together. No full merge should be needed.
His method extends two list co-ranking to many lists. It searches in index space, not value space. Per sequence bounds narrow to a consistent frontier. Runtime depends on log of total size and log of list count. Space stays linear in list count. Correctness follows from an exchange argument. Uses include parallel merge partitioning and multi stream joins.
Catalog record
| CREATOR | Amit Joshi [email protected] [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 19 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-22882
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge Journal: Information Processing Letters Amit Joshi [email protected] [email protected] Abstract We present a merge-free algorithm for multi-way co-ranking , the problem of computing cut indices i 1 , … , i m i_{1},\dots,i_{m} that partition each of the m m sorted sequences such that all prefix segments together contain exactly K K elements. Our method extends Siebert and Träff’s [ 3 ] [ 2 ] two-list co-ranking to arbitrary m 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 𝒪 ( log ( ∑ t n t ) log m ) \mathcal{O}(\log(\sum_{t}n_{t})\,\log m) time and 𝒪 ( m ) \mathcal{O}(m) space, independent of K K . We prove correctness via an exchange argument and discuss applications to distributed fractional knapsack, parallel merge partitioning, and multi-stream joins. 1 Introduction Problem. Given m sequences L_{1},\dots,L_{m} , each sorted in non-decreasing order (duplicates allowed) by convention and a global target rank K\in\{0,\dots,N\} with N=\sum_{t}n_{t} , the multi-way co-ranking problem asks for cut indices i_{1},\dots,i_{m} such that: \sum_{t=1}^{m}i_{t}=K\quad\text{and}\quad\max_{t}\,\ell_{t}\;\leq\;\min_{t}\,r_{t}, where \ell_{t}=(i_{t}>0)\,?\,L_{t}[i_{t}-1]:-\infty and r_{t}=(i_{t}<n_{t})\,?\,L_{t}[i_{t}]:+\infty (sentinels at ends). Intuitively, the first i_{t} items of L_{t} are part of a global K -prefix (up to ties). Contributions. We introduce a merge-free, index-space algorithm that generalizes classic two-list co-ranking to arbitrary m : 1. We design an iterative donor/receiver greedy scheme driven by max-left (largest \ell_{t} ) and min-right (smallest r_{t} ) respectively and move mass between the two with the invariant that total mass always equals K . We store explicit upper and lower bounds for each list Lb_{t}\leq i_{t}\leq Ub_{t} . 2. We show that halving the lower or upper range of the donor or receiver during each iteration yields fast convergence ( Lb_{t}=i_{t}=Ub_{t} ) in just \mathcal{O}\!\Big(\log(\!\sum_{t}n_{t})\Big)\text{ iterations.} 3. We use indexed (addressable) heaps to efficiently query \ell_{t} and r_{t} each iteration, and achieve a clean complexity bound independent of K : \mathcal{O}\!\Big(\log(\!\sum_{t}n_{t})\cdot\log m\Big)\text{ time,}\qquad\mathcal{O}(m)\text{ space.} 4. We give an exchange-style correctness proof: among all feasible infinitesimal transfers, moving mass from max-left to min-right achieves maximal progress on a natural imbalance potential, and any optimal correction sequence can be reordered so extremal transfers happen first without loss. 5. We discuss applications : distributed fractional knapsack (multi-source), parallel merge partitioning, and multi-stream join partitioning. Why index space? Many selection approaches reason in value space: merge the streams, maintain a heap of cursor values, or biselect a numeric threshold. Our method never merges or searches the value domain; it reasons only on indices and the relative order that the sorted property guarantees. This aligns with co-ranking’s roots [ 2 ] and leads to a deterministic, K -independent complexity, just like in [ 3 ] . 2 Background and Related Work Two-list co-ranking (partitioners for merge). Siebert and Traff’s [ 2 ] co-ranking for two sorted inputs (used to partition work in parallel merge) finds (j,k) s.t. j+k=i and the order constraints across the merge frontier hold. Efficient implementations do a binary-search-like halving of the feasible interval, yielding \mathcal{O}(\log n+\log m) time for the i -th output frontier. Siebert later used 2-way co-ranking work in [ 3 ] to create an in-place merge-sort, but again among only 2 sorted sequences. Our work generalizes the partitioner from 2-way to m -way, in index space and neatly describes the changes needed to do so. Splitter-based parallel sorting (Siebert & Wolf). Siebert and Wolf [ 4 ] introduced an exact splitter-finding method for scalable parallel sorting. Their algorithm computes p-1 splitter values that partition the global key space so each process receives an equal share of elements, achieving O(\tfrac{n}{p}\log n+p\log^{2}n) time. This approach operates entirely in value space : it searches for key thresholds that balance partitions during redistribution. By contrast, our multi-way co-ranking algorithm operates in index space on already-sorted sequences and directly outputs the co-rank vector (i_{1},\dots,i_{m}) satisfying \sum i_{t}=K and \max\ell_{t}\leq\min r_{t} , without any global value search. Splitters compute thresholds; co-ranking computes frontier indices and partitions sequences into prefixes and suffixes independent of values. Selection in sorted partitions (Frederickson–Johnson). A classical line of work due to Frederickson and Johnson [ 1 ] studies selection and ranking over structured inputs such as the union of m sorted lists (“sorted partitions”). Their algorithms are fundamentally value-space procedures: they maintain numeric thresholds (candidate keys), repeatedly count how many elements are \leq a threshold across the lists (via one-sided searches), and narrow the feasible value interval until the K -th value is identified. In the multi-list setting this yields bounds of the form O\!\big(m+\sum_{t=1}^{m}\log n_{t}\big) for selecting the K -th smallest from m sorted lists, with closely related results for ranking a given key [ 1 ] . By contrast, our contribution is an index-space primitive: we do not search the key domain or perform global “count- \leq ” operations. Instead, we directly evolve the per-sequence cut indices (i_{1},\dots,i_{m}) satisfying \sum_{t}i_{t}=K and the co-rank frontier condition, using only local comparisons at the current indices. Thus, while both approaches address “ K -th from multiple sorted sources”–type problems, Frederickson–Johnson output a value via thresholding, whereas we output the full co-rank vector without value bisection. This paper’s positioning. We treat multi-way co-ranking as a merge-free partitioning primitive that is an efficient and simple generalization of 2-way co-ranking described in [ 2 ] . The novelty is methodological (efficient indexed heaps for fast updates, explicit upper and lower bounds) and conceptual (the dynamics of halving the feasible range, operating in index-space), with applications in fast queries in distributed environments, databases, and parallel partitioning and/or merging of data. 3 Preliminaries and Notation We have m sorted sequences L_{t} of lengths n_{t} , total N=\sum_{t}n_{t} , and a target rank K\in[0,N] . We maintain an index vector i=(i_{1},\dots,i_{m}) with feasibility bounds Lb[t]\leq i[t]\leq Ub[t],\qquad\sum_{t}i[t]=K. Lower bounds Lb are initialized at 0 . Upper bounds Ub are initialized at n_{t} . We define left/right boundary values with sentinels on the ends: \ell_{t}=\begin{cases}(-\infty,t)&i_{t}=0\\ (L_{t}[i_{t}-1],t)&\text{else}\end{cases}\qquad r_{t}=\begin{cases}(+\infty,t)&i_{t}=n_{t}\\ (L_{t}[i_{t}],t)&\text{else}\end{cases} The co-rank condition is \max_{t}\ell_{t}\leq\min_{t}r_{t} . In cases of ties, we adopt a simple canonical convention: lower list indices are treated as “smaller,” so this ordering applies consistently in both the min-heap and max-heap. For the max-heap, this means that if two boundary values are equal, the element from the later list index is considered “larger” and will be returned first. This tie-breaking rule is purely conventional and ensures deterministic behavior; if the specific ordering of equal elements is irrelevant to an application, the tie-handling condition may be omitted altogether. If the co-rank condition is not satisfied, we select a donor p and receiver q . We define the donor slack to be i[p]-Lb[p] — how much p can donate before hitting its lower bound. Similarly, we define the receiver "slack" to be Ub[q]-i[q] how much mass q can receive before hitting its upper bound. We tighten at least one of these bounds on every iteration after the first one. 4 Data Structure: Indexed (Addressable) Heaps We maintain two indexed heaps over the fixed ID set \{0,\dots,k-1\} : 1. HL: a max-heap on keys (\ell_{t},t) , returning