\section{Introduction}\label{sec:classical} We consider comparison sorting of $n$ distinct labelled keys.\footnote{Throughout, $\log$ denotes $\log_2$, and $\ln$ the natural logarithm. We assume $n\ge2$.} A sorting algorithm (or \textit{sorter}, for short) chooses each pair using the answers to its earlier comparisons and must be correct for every strict total order on the labels. A sorting adversary supplies those answers as the comparisons arrive. The sorting adversary is \emph{legal} if every finite sequence of its answers is consistent with at least one total order. The adversary knows $n$ and sees the comparisons, but it need not inspect the sorter that generates them. The classical \emph{information-theoretic lower bound} (ITLB) shows that any sorter must perform $\ceil{\log(n!)}=n\log n-O(n)$ comparisons in the worst case~\cite[Section~5.3.1]{knuth}. This bound guarantees the existence of a hard input for every correct sorter. Here the problem is to produce hard answers by one \emph{deterministic, polynomial-time} adversary algorithm. Kaplan, Zamir, and Zwick~\cite[Section~7]{kzz-min} ask whether an efficient deterministic adversary can force $(1-\varepsilon)n\log n$ comparisons for every $\varepsilon>0$ and all sufficiently large $n$. The following theorem answers their question. \begin{theorem}\label{thm:main} There is a deterministic legal adversary, initialized using only $n$, that uses polynomially many bit operations per query and forces every correct sorter to make at least $(1-o(1))n\log n$ comparisons. \end{theorem} \begin{proof} See Section~\ref{sec:runtime}. \end{proof} We refer to an adversary satisfying Theorem \ref{thm:main} as an \textit{optimal} adversary. Without the restriction to polynomial-time, a deterministic optimal adversary is immediate. With randomness, simple, polynomial-time adversaries achieve optimality in both expectation and with high probability, just by generating random permutations. \paragraph{Deterministic adversaries without the polynomial-time restriction} If an adversary need not operate in polynomial-time, an optimal deterministic adversary is a simple book-keeping exercise. The adversary must simply keep all total orders consistent with the answers so far. Each comparison partitions them into two classes. The adversary answers so as to retain a larger class. After $q$ comparisons, at least $n!/2^q$ orders remain, forcing $q\ge\log(n!)$. This rule is deterministic, but enumerating its classes may require factorial work. The total orders consistent with the answers are the \emph{linear extensions} of the resulting partial order. Counting these extensions exactly is $\#\mathrm P$-complete~\cite{brightwell}. \paragraph{Deterministic adversaries in polynomial-time} Kahn and Kim~\cite{kahn-kim} already give a deterministic polynomial-time adversary for sorting with partial information. Starting from any given partial order $P$, it answers comparisons online and forces $\frac{1}{2}\log e(P)$ comparisons, where $e(P)$ is the number of linear extensions of $P$, and thus $\frac{1}{2}n \log n-O(n)$ for ordinary sorting. We note that, for ordinary sorting, the much simpler adversary of Brodal et al \cite{brodal} achieves the same guarantee. \paragraph{With randomness} If randomness is allowed, an optimal, polynomial-time adversary is a simple matter of generating a single uniformly random permutation. After choosing such a permutation the adversary simply answers from the ranks in that permutation. For every fixed correct sorter, the usual comparison-tree argument gives at least $\log(n!)$ comparisons in expectation and $\log(n!)-O(\log n)$ comparisons with probability $1-o(1)$. \paragraph{Randomized approximation of the number of linear extensions.} Randomization also makes it possible to estimate how many linear extensions remain after each possible answer. Given the current partial order $P$, assign each label a real coordinate in $(0,1)$ and form the region \[ K(P)=\{X\in(0,1)^n:X_i