Metraipolis › archive › dc_b2d22735daef

A Near-Optimal Generalized Sorting Algorithm — arXiv:2611.08397

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.08397
License (as archived)
CC0-1.0
Archived
2026-11-06T14:54:27.362Z
SHA-256 of the archived text
b8d4525c8a70f779f9872d0736ce76acf1f89b53126ee64dd3ebff90de620c35
Stable URL of this page
https://metraipolis.com/documento/dc_b2d22735daef

How to cite

A Near-Optimal Generalized Sorting Algorithm — arXiv:2611.08397 — arXiv (en), https://arxiv.org/abs/2611.08397 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b2d22735daef (Metraipolis archive dc_b2d22735daef, sha256 b8d4525c8a70f779f9872d0736ce76acf1f89b53126ee64dd3ebff90de620c35)
BibTeX
@misc{dcb2d22735daef,
  title = {A Near-Optimal Generalized Sorting Algorithm — arXiv:2611.08397},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.08397},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b2d22735daef; sha256 b8d4525c8a70f779f9872d0736ce76acf1f89b53126ee64dd3ebff90de620c35},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.08397. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We continue the study of the classic \emph{generalized sorting problem}, a basic variant of ordinary sorting. There are $n$ elements and an (initially hidden) total ordering $\pi$ over them. Unlike in ordinary sorting, however, only \emph{some} comparisons are allowed: those given by the edges of an undirected graph $G = (V, E)$ on the elements. How many comparisons are needed to find the total ordering? In ordinary sorting, $\Theta(n \log n)$ comparisons are necessary and sufficient. For generalized sorting, however, the best known upper bound has been $\tilde{O}(n^{3/2})$ since the work of Huang, Kannan, and Khanna (FOCS 2011), who even asked whether the problem might in fact require $n^{1+\Omega(1)}$ comparisons. We show that it does not: we give a randomized algorithm that uses $O(n \log^4 n)$ comparisons in expectation. Thus, up to logarithmic factors, generalized sorting is no harder than ordinary sorting.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.08397 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:26:57.634Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).