\documentclass[11pt,a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern,amsmath,amssymb,amsthm,mathtools}
\usepackage[a4paper,margin=25mm,headheight=15pt]{geometry}
\usepackage{microtype,booktabs,array,enumitem,xcolor,fancyhdr,needspace}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning,calc}
\usepackage[colorlinks=true,linkcolor=blue!40!black,citecolor=blue!40!black,urlcolor=blue!40!black]{hyperref}
\usepackage[nameinlink,noabbrev]{cleveref}
\definecolor{ink}{HTML}{183447}
\definecolor{accent}{HTML}{176B83}
\definecolor{pale}{HTML}{EDF4F6}
\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt plus 1pt}
\setlist{nosep,leftmargin=1.7em,topsep=4pt}
\pagestyle{fancy}
\fancyhf{}
\fancyhead[L]{\small\color{ink}Deferred separation}
\fancyhead[R]{\small\color{ink}Nicholas Nash}
\fancyfoot[C]{\thepage}
\renewcommand{\headrulewidth}{0.3pt}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\vol}{\operatorname{vol}}
\newcommand{\Prb}{\mathbb P}
\newcommand{\E}{\mathbb E}
\newcommand{\R}{\mathbb R}
\newcommand{\ceil}[1]{\left\lceil #1\right\rceil}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\half}{\tfrac12}
\DeclareMathOperator{\dist}{dist}
\newcommand{\guide}[2]{\begin{center}\fcolorbox{accent!35}{pale}{\begin{minipage}{0.91\textwidth}\textbf{\color{ink}#1}\quad #2\end{minipage}}\end{center}}
\hypersetup{pdftitle={An Optimal Deterministic Adversary for Sorting},pdfauthor={Nicholas Nash},pdfsubject={A top-down, self-contained presentation of the deterministic recursive sorting adversary}}
\title{An Optimal Deterministic Adversary for Sorting}
\author{Nicholas Nash\\[3pt]{\small\href{https://orcid.org/0009-0003-0475-7852}{ORCID: 0009-0003-0475-7852}}}
\date{7 November 2026}
\newcommand{\logtwo}{\log_2}
\begin{document}
\maketitle
\begin{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))n\logtwo n$ comparisons. The best previously known
adversary forced $\frac{37}{64}n\logtwo n$ comparisons.
The adversary recursively moves items into ordered subproblems, extending the
classical framework in which items move down a binary tree.
\end{abstract}

\section*{Methodological disclosure}
Except for the abstract, the text of this paper is AI-generated using
GPT 6 Astra. The author is working on a clear, human-readable exposition.

\guide{The organizing idea}{Keep comparisons inside a group for as long as
 they remain inexpensive to handle. When necessary, fix a position in that
 group and continue the unresolved order in a child.}

The paper first specifies the algorithm and its numerical subroutines.
Sections~\ref{sec:legal}--\ref{sec:accounting} establish legality and the
refinement bound; Sections~\ref{sec:repairs}--\ref{sec:runtime} give the repairs
and polynomial-time implementation. The appendices prove the numerical
subroutines independently of sorting.

\input{sections/deferred-separation}
\end{document}