HEXAGONbeta

An Optimal Deterministic Adversary for Sorting

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

Contributed by Nicholas Nash ↗

Version 2 / 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 deterministic polynomial-time adversary forced 3764nlog⁡2n\frac{37}{64}n\log_2 n comparisons. The adversary maintains a family of orders consistent with the answers so far, using a hierarchy of directed acyclic graphs. Bounds on vertex degrees and directed path lengths allow comparison answers to be chosen through deterministic calculations on small graph neighborhoods.

Author comments: Substantially revised and expanded exposition, with explicit algorithms, intuitive explanations of the main proofs, and further consequences. 36 pages. Source and Lean formalization: https://github.com/nicknash/sorting-adversary-proofs .

Provenance statement

The adversary and its analysis are due to AI (GPT 6 Astra). The human author shaped the exposition and abstractions, and reviewed the paper except for the appendices. Some parts, but not all, have been checked and understood by a human. A Lean formalization is available at https://github.com/nicknash/sorting-adversary-proofs .

Tools used

OpenAI
ChatGPTVersion GPT 6 Astra

References

  1. Donald E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching. Second edition, Addison-Wesley, 1998. Publisher's page (https://www.informit.com/store/art-of-computer-programming-volume-3-sorting-and-searching-9780201896855).link
  2. Michael L. Fredman. How good is the information theory bound in sorting? Theoretical Computer Science 1(4), 355--361, 1976. doi:10.1016/0304-3975(76)90078-5 (https://doi.org/10.1016/0304-3975(76)90078-5).DOI
  3. Mikhail J. Atallah and S. Rao Kosaraju. An adversary-based lower bound for sorting. Information Processing Letters 13(2), 55--57, 1981.
  4. Allan Borodin, Leonidas J. Guibas, Nancy A. Lynch, and Andrew C. Yao. Efficient searching using partial ordering. Information Processing Letters 12(2), 71--75, 1981. doi:10.1016/0020-0190(81)90005-3 (https://doi.org/10.1016/0020-0190(81)90005-3).DOI
  5. Dana Richards and Pravin M. Vaidya. On the distribution of comparisons in sorting algorithms. BIT 28, 764--774, 1988. Authors' paper (https://lic225.github.io/vaidya/sorting_BIT88.pdf).link
  6. 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. Authors' report, BRICS RS-96-40 (https://www.brics.dk/RS/96/40/BRICS-RS-96-40.pdf).link
  7. Haim Kaplan, Or Zamir, and Uri Zwick. The amortized cost of finding the minimum. Proceedings of the Twenty-Sixth Annual ACM--SIAM Symposium on Discrete Algorithms (SODA), 757--768, 2015. Published online 22 December 2014. doi:10.1137/1.9781611973730.51 (https://doi.org/10.1137/1.9781611973730.51). Authors' paper (https://zamir.prof/pub/FindMin_OrZamir.pdf).DOI
  8. 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).DOI
  9. 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
  10. Graham Brightwell and Peter Winkler. Counting linear extensions. Order 8(3), 225--242, 1991. doi:10.1007/BF00383444 (https://doi.org/10.1007/BF00383444).DOI
Show all 24 referencesShow fewer references
  1. Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM 38(1), 1--17, 1991. doi:10.1145/102782.102783 (https://doi.org/10.1145/102782.102783). Authors' manuscript (https://www.math.cmu.edu/~af1p/Texfiles/oldvolume.pdf).DOI
  2. Jeff Kahn and Jeong Han Kim. Entropy and sorting. Journal of Computer and System Sciences 51(3), 390--399, 1995. doi:10.1006/jcss.1995.1077 (https://doi.org/10.1006/jcss.1995.1077).DOI
  3. András Prékopa. On logarithmic concave measures and functions. Acta Scientiarum Mathematicarum 34, 335--343, 1973. Publisher's paper (https://acta.bibl.u-szeged.hu/14411/1/math_034_335-343.pdf).link
  4. Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël M. Jungers, and J. Ian Munro. An efficient algorithm for partial order production. SIAM Journal on Computing 39(7), 2927--2940, 2010. doi:10.1137/090759860 (https://doi.org/10.1137/090759860). Authors' manuscript (https://arxiv.org/abs/0811.2572).DOI
  5. Ivor van der Hoog, Irina Kostitsyna, Maarten Löffler, and Bettina Speckmann. Preprocessing ambiguous imprecise points. 35th International Symposium on Computational Geometry (SoCG), LIPIcs 129, 42:1--42:16, 2019. doi:10.4230/LIPIcs.SoCG.2019.42 (https://doi.org/10.4230/LIPIcs.SoCG.2019.42).DOI
  6. Ivor van der Hoog, Irina Kostitsyna, Maarten Löffler, and Bettina Speckmann. Sorting under partial (interval order) information. Journal of Computational Geometry 15(1), 143--171, 2024. doi:10.20382/jocg.v15i1a6 (https://doi.org/10.20382/jocg.v15i1a6).DOI
  7. Federico Ardila, Thomas Bliem, and Dido Salazar. Gelfand--Tsetlin polytopes and Feigin--Fourier--Littelmann--Vinberg polytopes as marked poset polytopes. Journal of Combinatorial Theory, Series A 118(8), 2454--2462, 2011. doi:10.1016/j.jcta.2011.06.004 (https://doi.org/10.1016/j.jcta.2011.06.004). arXiv:1008.2365 (https://arxiv.org/abs/1008.2365).arXivDOI
  8. Ferenc Bencs and Guus Regts. Approximating the volume of a truncated relaxation of the independence polytope. Discrete & Computational Geometry 76, 508--525, 2026. doi:10.1007/s00454-026-00824-y (https://doi.org/10.1007/s00454-026-00824-y).DOI
  9. Swee Hong Chan and Igor Pak. Linear extensions of finite posets. EMS Surveys in Mathematical Sciences, published online 17 March 2025. doi:10.4171/EMSS/97 (https://doi.org/10.4171/EMSS/97). Authors' manuscript (https://www.math.ucla.edu/~pak/papers/LEsurvey11.pdf).DOI
  10. Topi Talvitie, Kustaa Kangas, Teppo Niinimäki, and Mikko Koivisto. A scalable scheme for counting linear extensions. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI), 5119--5125, 2018. Publisher's page (https://www.ijcai.org/proceedings/2018/710). Authors' paper (https://ijcai.org/proceedings/2018/0710.pdf).link
  11. Bernhard Haeupler, Richard Hladík, John Iacono, Václav Rozhoň, Robert E. Tarjan, and Jakub Tětek. Fast and simple sorting using partial information. Proceedings of the Thirty-Sixth Annual ACM--SIAM Symposium on Discrete Algorithms (SODA), 2025. doi:10.1137/1.9781611978322.134 (https://doi.org/10.1137/1.9781611978322.134). Authors' manuscript (https://arxiv.org/abs/2404.04552).DOI
  12. Daniel Rutschmann. Sorting under partial information with optimal preprocessing time via unified bound heaps. Preprint, 2026. To appear at FOCS 2026. arXiv:2604.12653 (https://arxiv.org/abs/2604.12653).arXiv
  13. Mark Huber. Near-linear time simulation of linear extensions of a height-2 poset with bounded interaction. Chicago Journal of Theoretical Computer Science 2014, Article 3, 1--16. doi:10.4086/cjtcs.2014.003 (https://doi.org/10.4086/cjtcs.2014.003).DOI
  14. James G. Propp and David B. Wilson. Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures & Algorithms 9(1--2), 223--252, 1996. Authors' paper (https://www.stat.berkeley.edu/~aldous/206-RWG/RWGpapers/propp_wilson.pdf).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.SupersededNov 07, 2026
  2. v2 · 36 pagesSubmitted by Nicholas NashSubstantially revised and expanded exposition, with explicit algorithms, intuitive explanations of the main proofs, and further consequences. 36 pages. Source and Lean formalization: https://github.com/nicknash/sorting-adversary-proofs .CurrentNov 11, 2026