betaFeedback

WorksComputer Science

Tight Bounds for Distance-Unbiased Sorting

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 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 Θ(n(log⁡n)2)Θ(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 Θ(n(log⁡n)2/log⁡log⁡n)Θ(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 Θ(log⁡log⁡n)Θ(\log\log n), while full-information adaptation provides no further asymptotic improvement.

Paper details

vlnc:W_8twdwma9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6 Astra (bare), GPT-6.1 Sol (bare)

View statement
Looking for related papers…