\section{Running time}\label{sec:runtime}\label{sec:parameter-selection}

\texttt{Select} and \texttt{ChooseAnchor} inspect neighborhoods in an
order-restriction DAG whose sizes depend only on $k$. Their cost also
depends on the precision of the interval endpoints. The following lemma
bounds the number of digit assignments they enumerate and the precision
of the anchors they return.

\begin{lemma}[Cost of \texttt{Select} and \texttt{ChooseAnchor}]\label{lem:local-cost}
For \textnormal{\texttt{Select}} and \textnormal{\texttt{ChooseAnchor}}
under the assumptions of Lemmas~\ref{lem:local-routines}
and~\ref{lem:anchor-selection}, there is a computable
budget $E_k$, depending only on $k$, such that each call enumerates at
most $E_k$ digit assignments. If the stored interval bounds have at most
$\Lambda$ fractional binary digits, every returned anchor has at most
$\Lambda+\log E_k$ such digits.
\end{lemma}
\begin{proof}
See Theorem~\ref{thm:local} and Appendix~\ref{app:arithmetic}.
\end{proof}

A fixed program generates the parameters and $E_k$ for
$k=64,128,\ldots$, writing each completed tuple in binary. On input
size $n$, run this program for $n$ steps and choose the largest completed
$k$ with $E_k\le n$, denoted by $k(n)$. If no such value exists, answer from the fixed label
order. The simulation writes at most $n$ bits, so parsing its output
and selecting a tuple also take polynomial time.

For every $k$ in this sequence, both its generation time and $E_k$ are finite.
That tuple therefore qualifies for all sufficiently large $n$, proving
$k(n)\to\infty$.\footnote{These parameters give an asymptotic guarantee,
with no claim of practical running time.} Appendix~\ref{app:arithmetic}
shows that the interval endpoints require polynomially many bits, and
that tree traversal and updates to the in-node DAGs take polynomial time.
Each comparison calls \texttt{Select} at most three times and
\texttt{ChooseAnchor} at most $n$ times, giving a fixed polynomial bound
on bit operations per query, independent of the length of the interaction.

\begin{proof}[Proof of Theorem~\ref{thm:main}]
The adversary is deterministic and polynomial-time. The fixed label
order gives legal answers, and legality for every parameter $k\ge64$
follows from Theorem~\ref{thm:fixed-stage}. For sufficiently large $n$,
the procedure above selects a value $k(n)$ with $E_{k(n)}\le n$.
A correct sorter can then stop only when $T_q=1$, which requires
\[
q\ge\frac{\log(n!)}{1+\delta_{k(n)}}=(1-o(1))n\log n,
\]
since $\delta_k=O(\log k/k)$ and $k(n)\to\infty$.
\end{proof}