Skip to content
Preprint

Tight Bounds for Distance-Unbiased Sorting

Nov 2026 · 0 citations · 17 references
Computer Science

Abstract

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 exchange distances but sample uniformly among all pairs at each chosen distance. For static rules, we prove that the optimal worst-case high-probability runtime is $\Theta(n(\log n)^2)$. This establishes the asymptotic optimality of the harmonic sorter within this class and partially resolves an open question of Olesker-Taylor. We then allow the distance distribution to change either according to a predetermined schedule or adaptively using the current permutation and the entire history. Matching upper and lower bounds show that both classes have optimal runtime $\Theta(n(\log n)^2/\log\log n)$. Thus, scheduled adjustments of the distance distribution improve the optimal static worst-case runtime by a factor of $\Theta(\log\log n)$, while full-information adaptation provides no further asymptotic improvement.

View source

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