CS Paper Radar

Sorting in PRAM, Parallel Comparison Model and Parallel External Memory Model

Gopalan Sajith, Manas Kumar Panda, Ranajit Senko

cs.DS ·submitted 2026-11-03 13:54 UTC · v1

Abstract

We study the problem of sorting on the Parallel Random Access Machine (PRAM), Parallel Comparison Model (PCM) and Parallel External Memory Model (PEM). On PRAM, we present a Concurrent Read Exclusive Write algorithm that runs in $O(\log n)$ time with $n$ processors; our algorithm is very different from Cole's Merge Sort. On PCM, we present the first optimal algorithm for sorting after AKS; our algorithm runs in $O(\log n/\logα)$ comparison rounds with $nα$ processors, for $1\leqα\leq n$. On PEM, we present a Concurrent Read Exclusive Write algorithm that sorts $N$ elements in $O\left(\log\frac{N}{B}\right)$ I/O rounds with $p\geq \frac{N}{B}$ processors.

Closest papers

Nearest neighbours by meaning across the whole index.

Communication-Oblivious Permutation and Sorting

cs.DS ·2026-10-29 ·Qi Dong, Yilei Wang, Ke Yi
theory similarity 0.63
Abstract

With the help of secure hardware such as trusted execution environments (TEEs), private data can be uploaded and computed in untrusted cloud clusters, so that an adversary controlling the cloud can only see the data in encrypted form. However, the communication pattern between the processors may still reveal sensitive information about the data, so it is important to develop parallel algorithms in the BSP model whose communication pattern is independent of the input data, a property known as \textit{communication obliviousness}. In this paper, we study such algorithms for three fundamental problems: permutation, sorting, and 0-1 sorting. For the first two problems, we prove a tight (up to lower-order terms) communication complexity of $(2-2/p)n\pm o(n)$. Here, $p$ is the number of processors and $n$ is the input size, assuming $2\le p$ and $p=o(n^{1/3})$. Our lower bound holds regardless of the number of rounds and local memory size, while for balanced permutation and sorting the upper bound is achieved in a constant number of rounds with load at most $n/p+o(n/p)$. For 0-1 sorting, we also derive a tight communication complexity of $C_{\mathrm{cut}}(p) \cdot n \pm o(n)$, where $C_{\mathrm{cut}}(p)$ is the optimal value of a linear program parameterized by $p$. Although there appears to be no closed-form for $C_{\mathrm{cut}}(p)$, we show that it is strictly smaller than $2-2/p$ for all $p\ge 3$, thus separating 0-1 sorting from general sorting in terms of their communication complexity.

0.28

Online and Fully-Dynamic Sorting

cs.DS ·2026-11-16 ·Yossi Azar, Sujoy Bhore, Devdan Dey, Debmalya Panigrahi, Or Vardi +1 more
theory similarity 0.60
Abstract

Online sorting asks how to place $n$ sequentially arriving elements in an array to minimize the sum of absolute differences between consecutive elements. Fully-dynamic sorting further extends the problem to allow both element insertions and deletions. Without recourse, these problems face strong lower bounds on the competitive ratio: $Ω(\sqrt{n})$ for online sorting and $Ω(n)$ for fully-dynamic sorting. In sharp contrast, we show that allowing only poly-logarithmic recourse yields at least exponential improvements in the competitive ratio for both problems:(1) Our main algorithmic result is a deterministic fully-dynamic sorting algorithm that is $O(\log^2 n)$-competitive and has $O(\log^4 n)$ amortized recourse per update. We complement this with a lower bound showing that any deterministic algorithm with any $O(\mathrm{polylog}(n))$ competitive ratio has amortized recourse at least $Ω(\sqrt{\log n})$.(2) For the insertion-only setting, we establish a family of approximation--recourse tradeoffs, including $O(\log\log n)$ competitive ratio with $O(\log\log n)$ amortized recourse. Given the lower bound in the fully-dynamic case, this result shows that the insertion-only problem yields exponentially better bounds than the fully-dynamic one.(3) Finally, we show that the stronger approximation-recourse tradeoff for the insertion-only case extends to the fully-dynamic setting when the array has $(1+\varepsilon)n$ space.

0.12

Differentially Oblivious Priority Queues with Sublogarithmic Cost

cs.DS cs.CC ·2026-11-03 ·Zimai Guo, Cheng Hong, Zhechen Li
theoryhot direction similarity 0.59
Abstract · 38 pages, 1 figure

In this paper, we study exact online integer priority queues under differential obliviousness in the balls-and-bins model. Given a public upper bound $T$ on the number of operations and assuming that the priorities are bounded by a polynomial in $T$, we construct an $(\eps,δ)$-differentially oblivious priority queue supporting insertion and minimum extraction, which requires $\polylog(T)$ private memory. For constant $\varepsilon>0$ and $δ=\exp(-Θ(\log^2 T))$, our construction incurs $O(\log T/\log\log T)$ expected amortized total work per operation, which breaks the $Ω(\log T)$ barrier for fully oblivious priority queues~[Jacob et al., SODA'2019]. Further, we prove a matching lower bound for $(\eps,δ)$-differentially oblivious priority queues with $\varepsilon=O(1)$ and $δ=o(1)$, which indicates that our construction is asymptotically optimal in terms of total work.

0.36

Undirected Multiple-Unicast Network Coding and Faster External-Memory Integer Sorting

cs.DS cs.CCcs.IT ·2026-10-14 ·Baochun Li, Zongpeng Li, Sirui Liu
code/data similarity 0.57
Abstract · 43 pages, 4 figures, 1 table. Lean 4 formalization and verification code: https://github.com/rtyu-1/coded-sorting-lean

In undirected multiple-unicast networks, where independent messages are sent between specified source--destination pairs, network coding allows intermediate nodes to combine messages, whereas fractional routing splits and forwards individual messages along paths without mixing them. Proposed in 2004 by Li and Li and independently by Harvey, Kleinberg, and Lehman, the multiple-unicast conjecture---a central conjecture in network coding with deep connections to computational complexity---asserts that network coding and fractional routing have the same achievable rate region. We construct a counterexample refuting this conjecture and use it to reduce block transfers in external-memory data rearrangement, thereby accelerating external-memory integer sorting and answering in the affirmative the longstanding question of Aggarwal and Vitter (1988) on whether integer operations can beat the comparison-sorting input/output (I/O) bound. Specifically, we give a deterministic sorting algorithm: for $N$ integers of $Θ(\log N)$ bits, a memory holding $M$ integers, and block transfers of $B$ integers, where $2B\le M\le N$, the number of block transfers is \[ O\!\left(\frac{N}{B}\left[1+ \frac{\log N}{(\log(M/B))^{1-\varepsilon}(\log M)^\varepsilon} \right]\right), \] where $\varepsilon=1.5\times10^{-5}$ is an absolute constant. This bound asymptotically improves on the classical $Θ\!\left(\frac{N}{B}\left[1+ \frac{\log(N/M)}{\log(M/B)}\right]\right)$ comparison-sorting bound in certain parameter regimes. Under the external-memory model specified in this paper, we have formally verified the algorithm's correctness and I/O complexity bound in Lean~4.

0.57

Straightforward Entropy-Sensitive Mergesort

cs.DS ·2026-08-11 ·Bill Jin, Alex Zihan Xu
similarity 0.55
Abstract · 21 pages, 15 pages main text, 4 pages appendix, 2 figures

In this paper, we present a stable mergesort variant, "directional mergesort", that to sort an array of $n$ elements makes no more than $nH+3n$ comparisons and $1.5nH+O(n)$ moves where $H$ is the run-based entropy of the input sequence, matching the best existing algorithms in run-adaptive sorting. However, our algorithm is surprisingly minimalistic: it leverages only skip checks, i.e., bypassing the merge step when both halves are already in order, and dynamically changing the direction of merging based on the state of the subarrays. As dynamic run scanning is avoided, all merge steps remain static and derivable from $n$, enabling a reduction to $O(1)$ words of stack space (i.e. space usage excluding the merge buffer) in "directional mergesort$^{++}$", thus improving over the predecessors' $O(\lg n)$ words. Importantly, as directional mergesort adapts only to non-decreasing runs, directional mergesort$^{++}$ also applies a parallel set of rules for (strictly) decreasing runs, allowing the algorithm to also adapt to decreasing runs whilst retaining the original comparison bounds.

0.10

A Parallel Greedy Algorithm for Maximal b-Matching in Hypergraphs

cs.DS cs.DC ·2026-11-11 ·Saeed Bakhshan, Daniel Grosu, Henrik Reinstädtler, Christian Schulz
published similarity 0.55
Abstract · 19 pages. Accepted to the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA 2027)

We present \parallelBatchBMatch, a parallel batch-vote algorithm for maximal $b$-matching in hypergraphs. The algorithm is deterministic for a given ordering of edges and produces the same output as the sequential greedy algorithm, i.e., the lexicographically first maximal $b$-matching. Under a uniformly random priority order it performs $O(m')$ expected work in the binary fork--join model, where $m'$ is the number of pins, the total number of vertex--edge incidences. The algorithm performs at most $m$ rounds for every priority order, where $m$ is the number of edges. Every round of the algorithm has $O(\log^2 m')$ depth with high probability, and thus the total depth of the algorithm is $O(m \log^2 m')$ with high probability. We implement the parallel algorithm in CUDA and evaluate it on real-world hypergraphs with capacities $b \in \{1, 3, 5\}$. The parallel algorithm computes the same matchings as the greedy algorithms and for the case of $b = 5$ it is up to $19.07$ times faster than the existing state-of-the art greedy algorithm.

0.38

Adaptive Sorting, also in the BST Model

cs.DS ·2026-10-11 ·Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
theory similarity 0.55
Abstract

Sorting is one of the most basic algorithmic problems. Adaptive sorting algorithms exploit features that make an input easier to sort, often captured by entropy measures. Many such measures have been studied, raising two natural questions: how do they relate to one another, and are there algorithms that are adaptive to them? We complete a hierarchy of relations between previously studied entropy measures and show that the classical measure Reg is a source of this hierarchy. We prove that an existing data structure yields a Reg-adaptive sorting algorithm, thereby achieving the adaptive bounds of every measure in the hierarchy. Following McIlroy's observation that Reg has a mathematically inconvenient definition, we study a slightly weaker but simpler measure, reg. For inputs without duplicates, we show that O(n + log reg) = O(n + log Reg), so this simplification preserves the adaptive bound. Finally, we do algorithms design and introduce SproutSort, a reg-adaptive algorithm in the offline binary search tree (BST) model. SproutSort achieves an access cost of O(n + log reg), making it the most adaptive algorithm in this model to date. We also introduce SkeletonSort, a simple randomised pointer-machine algorithm that sorts distinct keys in expected O(n + log reg) time, offering a considerably simpler implementation of a sorting algorithm this high in the adaptive hierarchy.

0.28

Upper and Lower Bounds on the Space Complexity of Multi-word Single-Writer Registers

cs.DC ·2026-08-19 ·Yuanhao Wei, Yousof Yavari
theory similarity 0.55
Abstract · Full version of paper appearing in DISC'26

We prove matching upper and lower bounds on the space complexity of simulating a large shared register using smaller shared registers. We focus on the case where both the simulated and base registers are single-writer, which means they can be accessed concurrently by multiple readers but only by a single writer. To strengthen our lower bounds, we prove that they hold even when the base registers are atomic and the simulated register is regular. Furthermore, the lower bounds hold for obstruction-free implementations, which means they also hold for lock-free and wait-free implementations. If $m$ is the number of values representable by the large register and $b$ is the number of values representable by each base register, our first lower bound says that any obstruction-free implementation that has an invisible reader requires at least $\lceil \frac{m-1}{b-1} \rceil$ base registers. A reader is considered invisible if it never writes to base registers. This lower bound is asymptotically tight for the invisible-reader case and represents an exponential improvement over the previous best known lower bound. For the general case, which allows any combination of visible and invisible readers, we prove a $\lceil \min(\frac{m-1}{b-1}, r+\frac{\log{m}}{\log{b}}) \rceil$ space lower bound, where $r$ is the number of readers. To show that this lower bound is asymptotically tight, we develop a wait-free algorithm for simulating a multi-word atomic register from atomic base registers using $Θ(r + \frac{\log{m}}{\log{b}})$ space. Combining this algorithm with known invisible-reader constructions gives a $Θ(\min(\frac{m}{b}, r + \frac{\log{m}}{\log{b}}))$ space upper bound. This improves upon the previously known space upper bound of $Θ(\min(\frac{m}{b}, r\frac{\log{m}}{\log{b}}))$.

0.32