{"ID":2849380,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.22882","arxiv_id":"2510.22882","title":"Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge","abstract":"We present a merge-free algorithm for multi-way co-ranking, the problem of computing cut indices $i_1,\\dots,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 \\emph{index-space}. The algorithm runs in $O(\\log(\\sum_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","short_abstract":"We present a merge-free algorithm for multi-way co-ranking, the problem of computing cut indices $i_1,\\dots,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 t...","url_abs":"https://arxiv.org/abs/2510.22882","url_pdf":"https://arxiv.org/pdf/2510.22882v1","authors":"[\"Amit Joshi\"]","published":"2025-10-27T00:17:14Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}