Skip to content
Preprint

A Near-Optimal Generalized Sorting Algorithm

Nov 2026 · 0 citations · 19 references
Computer Science

TL;DR

It is shown that up to logarithmic factors, generalized sorting is no harder than ordinary sorting, and a randomized algorithm is given that uses $O(n \log^4 n)$ comparisons in expectation.

Abstract

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.

View source

Similar papers

Preprint Nov 2026

Generalized Sorting via Four-Cycles

We study the generalized sorting problem where only a subset of the pairs can be compared. Equivalently, we are given an $n$-vertex $m$-edge graph $G=(V, E)$ where the vertex set $V$ is to be sorted, and the edge set $E$ indicates possible comparisons. The goal is to sort $V$ with as few (adaptive) queries to $E$ as po...

Soheil Behnezhad, Shane Ferrante · 0 citations
Preprint Nov 2026

Online and Fully-Dynamic Sorting

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 com...

Y. Azar, S. Bhore, Devdan Dey et al. · 0 citations
Preprint Oct 2026

Subset Sum in Almost-Linear Time

We give a deterministic algorithm for finding a subset of the input integers $1\le a_1,\ldots,a_n \le \Delta$ that sums to the target $t$ in $\mathcal{O}(n+\Delta^{1+o(1)})$ time. This improves upon the previous $\widetilde{\mathcal{O}}(n + \Delta^{1.5})$-time algorithm by Chen, Lian, Mao, and Zhang (SODA 2024), and ac...

Ce Jin, Xiao Mao · 2 citations
Preprint Nov 2026

Tight Bounds for Distance-Unbiased Sorting

We study elitist randomized local search for sorting permutations. In this model, each iteration considers a possible exchange of two positions. The entries are exchanged if and only if they are in the wrong order. We introduce \emph{distance-unbiased} selection rules, which may choose an arbitrary distribution over ex...

Mats Bierwirth, C. Doerr, J. Lengler · 0 citations
Preprint Sep 2026

Hamiltonicity of mildly pseudorandom regular graphs

We show that if an $(n,d,\lambda)$-graph satisfies $\lambda\leq (1-\delta)d$ and $d\gg \delta^{-6}(\log n)^{3}$ for some $\delta>0$, then it is Hamiltonian. A qualitatively similar result was recently proven by Brada\v{c} and Janzer. Our proof here is shorter and gives better quantitative bounds. \par In our proof, as...

Alp Muyesser · 0 citations
Preprint Oct 2026

Total $\{k\}$-domination in caterpillars: Structural properties and exact results

The total $\{k\}$-domination problem ($T\{k\}DP$) seeks a minimum-weight function such that the sum of weights in every open neighborhood is at least $k$. While this problem is known to be NP-hard for general graphs, we demonstrate that for the family of caterpillars, it simplifies to the classical total domination num...

M. Escalante, Paola B. Tolomei, María Inés Lopez Pujato · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.