HEXAGONbeta

An Optimal Deterministic Adversary for Sorting

Primarily AI-generated textHuman understanding: some partscs.DS — Data Structures and Algorithms

Contributed by Nicholas Nash ↗

Version 1 / Nov 10, 2026 / CC BY 4.0

Abstract

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))nlog⁡2n(1-o(1))n\log_2 n comparisons. The best previously known adversary forced 3764nlog⁡2n\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.

Provenance statement

Except for the abstract, the text is AI-generated using GPT 6 Astra. The author is working on a clear, human-readable exposition. Some parts, but not all, have been checked and understood by a human.

Tools used

OpenAI
ChatGPTVersion GPT 6 Astra

References

  1. Gerth Stølting Brodal, Shiva Chaudhuri, and Jaikumar Radhakrishnan. The randomized complexity of maintaining the minimum. Nordic Journal of Computing 3(4), 337--351, 1996. The binary adversary and its interval interpretation are reviewed in Section 2 and the introduction of kzz .
  2. Haim Kaplan, Or Zamir, and Uri Zwick. A sort of an adversary. Proceedings of the Thirtieth Annual ACM--SIAM Symposium on Discrete Algorithms (SODA), 1291--1310, 2019. doi:10.1137/1.9781611975482.79 (https://doi.org/10.1137/1.9781611975482.79). The discussion of continuous intervals and richer dependencies is in Section 6.DOI
  3. Richard P. Stanley. Two poset polytopes. Discrete & Computational Geometry 1, 9--23, 1986. doi:10.1007/BF02187680 (https://doi.org/10.1007/BF02187680). Author's copy (https://math.mit.edu/~rstan/pubs/pubfiles/66.pdf).DOI
  4. Nicholas Nash. Sorting adversaries in Lean. Lean 4 source repository, 2026. https://github.com/nicknash/sorting-adversary-proofs. Source snapshot 15d93dd , accessed 7 November 2026.link

Version history

  1. v1 · 22 pagesSubmitted by Nicholas NashSource, 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.CurrentNov 07, 2026