PaperfootJoin free
arXiv

Sorting can use fewer data transfers in some memory settings

The authors proved that an integer-sorting algorithm beat the data-transfer bound for comparison-based sorting in some parameter ranges as inputs grew.

Paper by Baochun Li, Zongpeng Li, Sirui Liu
An open blue cabinet holds ordered blocks and a simple black path, beside scattered blocks, interlocking paths, and a crowded gray compartment.
Preprint: method

Edited by Boris Djordjevic · Paperfoot

Paper

The paper gave a finite counterexample to a network conjecture and used its structure to prove a data-transfer guarantee for an integer-sorting algorithm in a formal memory model. The conjecture concerned independent messages traveling between multiple sender–receiver pairs over two-way links. It said combining messages offered the same achievable sending rates as splitting and forwarding them without combining different messages. The counterexample disproved that claim.

For sorting, the authors bounded transfers between external storage and working memory. In some ranges of memory and transfer-block sizes, their algorithm’s transfer bound grew more slowly with input size than the classical bound for sorting by comparing values. The authors formally verified the algorithm’s correctness and transfer bound in Lean, software for checking mathematical proofs.

Why it matters

The proof addressed a question posed in 1988: whether operations on integers can beat the data-transfer bound for comparison-based sorting. It established an advantage in some parameter ranges as inputs grow, rather than a measured speed gain.

Caveats

This preprint’s guarantees concerned the paper’s formal memory model, with memory holding at least two transfer blocks but no more than the full input. The integers’ bit length had to be proportional to the number of bits needed to write the input count; the abstract reported no measured runtime tests.

In this paper

external-memory integer sorting

Methods
Columnsortmost-significant-digit radix sorting
Links
Code

What it shows

Under the specified external-memory model, a deterministic algorithm sorts N integers of Θ(log N) bits using O(N/B[1+fraclog N(log(M/B))^(1-ε)(log M)^ε]) block transfers, where ε=1.5×10−5 is an absolute constant.

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≤ M≤ N, the number of block transfers is O(N/B[1+fraclog N(log(M/B))^(1-ε)(log M)^ε]), where ε=1.5×10−5 is an absolute constant.

Abstract

A finite binary linear block code achieves a common rate strictly above the routing upper bound on a finite undirected network with unit edge capacities and independent source messages.

A finite binary linear block code achieves a common rate strictly above this routing upper bound.

Theorem 3.2 (A strict coding advantage in undirected networks).

The external-memory integer sorting algorithm's correctness and I/O complexity bound are formally verified in Lean under the specified external-memory model.

Under the external-memory model specified in this paper, we have formally verified the algorithm's correctness and I/O complexity bound in Lean.

Abstract

When the input fits in memory, reading, sorting, and writing it takes optimal O(N/B) block transfers.

When the input fits in memory, reading, sorting, and writing it takes the optimal O(N/B) block transfers.

Theorem 3.1 (External-memory integer sorting).

Quoted word for word from the full text on arXiv.

The paper

Undirected Network Coding and Faster External-Memory Integer Sorting

Baochun Li, Zongpeng Li, Sirui Liu

arXiv, Oct 14, 2026, Open access, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.20079

arXiv:2610.20079v2 in cs.DS, also cs.CC, cs.IT, math.IT

AbstractPDFHTML

Comments: 34 pages, 5 figures. Revised construction and improved exponent

Cite as BibTeX
@misc{li2026undirected,
  title = {Undirected Network Coding and Faster External-Memory Integer Sorting},
  author = {Li, Baochun and Li, Zongpeng and Liu, Sirui},
  year = {2026},
  eprint = {2610.20079},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  doi = {10.48550/arxiv.2610.20079},
  url = {https://arxiv.org/abs/2610.20079}
}

Related