Nicholas Nash

cs.DS — Data Structures and Algorithms

An Optimal Deterministic Adversary for Sorting

Contributed by Nicholas Nash

This paper describes an optimal deterministic, polynomial-time adversary for ordinary sorting. For any correct sorting algorithm, the adversary forces that algorithm to make $(1-o(1))n\log_2 n$ comparisons. The best previously known adversary forced $\frac{37}{64}n\log_2 n$ comparisons. The adversary recursively moves items into ordered subproblems, extending the classical framework in which items move down a binary tree.

Author comments: Source, exact numerical checks, and related Lean 4 formalization: https://github.com/nicknash/sorting-adversary-proofs . The paper distinguishes this continuous-position presentation from the repository's earlier integer-colour construction.