\section{Related Work}\label{sec:related}\label{sec:related-work}

\subsection{Sorting with partial information}

Fredman~\cite{fredman} studied how closely sorting can approach the
information-theoretic lower bound when some orders have already been
excluded. For any nonempty family $\Gamma$ of permutations of $n$ items,
he showed that the unknown order can be identified using at most
$\log|\Gamma|+2n$ comparisons. In particular, if the available information
is a partial order $P$, this gives $\log e(P)+2n$ comparisons, where
$e(P)$ counts its linear extensions. The comparison bound is within an
additive $2n$ of the ITLB, but constructing the strategy requires
enumerative information about the possible orders and does not give a
polynomial-time algorithm for general partial orders~\cite[p.~390]{kahn-kim}.

Kahn and Kim~\cite{kahn-kim} later gave a deterministic polynomial-time
sorting algorithm using $O(\log e(P))$ comparisons. They also constructed
a deterministic polynomial-time adversary forcing $\Omega(\log e(P))$
comparisons. More recent work gives much faster algorithms for sorting
from supplied comparisons~\cite{haeupler-sorting,rutschmann-sorting}.
Our adversary faces the corresponding task of choosing
answers efficiently while forcing asymptotically the full ITLB for ordinary
sorting.

\subsection{Binary-tree adversaries}

Atallah and Kosaraju~\cite{atallah} gave an efficient sorting adversary with
a lower bound of $\tfrac12 n\log n$ comparisons. Related adversaries arose
in slightly different problems studied by Borodin, Guibas, Lynch, and
Yao~\cite{borodin}, Richards and Vaidya~\cite{richards}, and Brodal,
Chaudhuri, and Radhakrishnan~\cite{brodal}.
The binary-tree rule of Borodin et al. and Brodal et al. provides the
starting point for our construction.

Place every item at the root of an ordered binary tree. Items in disjoint
subtrees have the left-to-right order of those subtrees. A comparison changes
the placement as follows.
\begin{itemize}
\item If both items occupy the same node, move one to its left child and
the other to its right child, and answer accordingly.
\item If one item is at an ancestor of the other, move the higher item to
the child whose subtree does not contain the lower item.
\item If their nodes are unrelated by ancestry, answer from their
left-to-right order, without moving either item.
\end{itemize}
For a concrete example, start with $A,B,C,D$ at the root.
Answering $A<B$ moves $A$ to the left child and $B$ to the right, while
$C,D$ remain at the root. If the sorter next compares $A$ and $C$, the
ancestor rule moves $C$ to the right child and gives $A<C$.
Comparing $D$ and $B$ then moves $D$ to the left child and gives $D<B$.
The two children now contain $\{A,D\}$ and $\{B,C\}$.
A subsequent comparison of $D$ with $C$ is answered $D<C$ without moving
either item. The orders within $\{A,D\}$ and within $\{B,C\}$ remain
unresolved. Figure~\ref{fig:binary-example} shows the placements.

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[>=Latex,font=\small,
  group/.style={draw=ink!65,rounded corners=2pt,fill=pale,
                minimum height=7mm,minimum width=17mm}]
\begin{scope}[shift={(-3.4,0)}]
\node at (0,1.25) {After answering $A<B$};
\node[group] (root1) at (0,.5) {$C,\ D$};
\node[group] (left1) at (-1.3,-.75) {$A$};
\node[group] (right1) at (1.3,-.75) {$B$};
\draw[->] (root1)--(left1);
\draw[->] (root1)--(right1);
\end{scope}
\draw[->,thick,accent] (-.9,-.1)--(.9,-.1);
\begin{scope}[shift={(3.4,0)}]
\node at (0,1.25) {After also answering $A<C$ and $D<B$};
\node[circle,draw=ink,fill=white,minimum size=4mm] (root2) at (0,.5) {};
\node[group] (left2) at (-1.3,-.75) {$A,\ D$};
\node[group] (right2) at (1.3,-.75) {$B,\ C$};
\draw[->] (root2)--(left2);
\draw[->] (root2)--(right2);
\end{scope}
\end{tikzpicture}
\caption{The binary-tree adversary. The first comparison separates two
items at the same node. The next two comparisons each move an item from
an ancestor into the opposite child. In the final state, comparing $D$
with $C$ requires no movement.}
\label{fig:binary-example}
\end{figure}

Each comparison increases the sum of item depths by at most two.
At completion, occupied nodes must be distinct and unrelated by ancestry:
otherwise two represented items can occur in either relative order, leaving
an unresolved comparison. Associate the root with $(0,1)$, and associate
each child with the corresponding half of its parent's interval.
A node of depth $d_i$ therefore represents an interval of length $2^{-d_i}$.
At completion these intervals are disjoint, giving
\[
\sum_i2^{-d_i}\le1,
\qquad
2^{-\frac1n\sum_i d_i}\le\frac1n\sum_i2^{-d_i}\le\frac1n.
\]
Convexity gives the bound on $2^{-\frac1n\sum_i d_i}$. Hence $\sum_i d_i\ge n\log n$, and
at least $\tfrac12 n\log n$ comparisons are
necessary~\cite[Section~4.1]{brodal}.

The tree representation can settle relations that have never been queried.
For example, start again with four items at the root and answer $A<B$ and
$C<D$. Placing $A,C$ in the left child and $B,D$ in the right child also
commits the adversary to $A<D$ and $C<B$. Neither relation follows from
those two answers alone.

\subsection{The adversary of Kaplan, Zamir, and Zwick}

Kaplan, Zamir, and Zwick~\cite{kzz} use a four-child tree. Intermediate
states correspond to consecutive ranges of children, so an item can
narrow its range before entering a particular child. See Figure~\ref{fig:kzz-lattice}.

A key idea of this adversary is that a comparison between two items need not immediately cause them
to descend in the tree structure. Instead, pairs of items whose relative order is fixed can remain in the
same node.

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[>=Latex,font=\small,
  state/.style={draw=ink!65,rounded corners=2pt,fill=pale,
                minimum height=7mm,minimum width=15mm},
  leaf/.style={state,fill=white}]
\node[state] (n03) at (0,0) {$[0,3]$};
\node[state] (n02) at (-1.25,-1) {$[0,2]$};
\node[state] (n13) at (1.25,-1) {$[1,3]$};
\node[state] (n01) at (-2.5,-2) {$[0,1]$};
\node[state] (n12) at (0,-2) {$[1,2]$};
\node[state] (n23) at (2.5,-2) {$[2,3]$};
\node[leaf] (n0) at (-3.75,-3) {$0$};
\node[leaf] (n1) at (-1.25,-3) {$1$};
\node[leaf] (n2) at (1.25,-3) {$2$};
\node[leaf] (n3) at (3.75,-3) {$3$};
\foreach \a/\b in {n03/n02,n03/n13,n02/n01,n02/n12,n13/n12,n13/n23,n01/n0,n01/n1,n12/n1,n12/n2,n23/n2,n23/n3}
  \draw[->] (\a)--(\b);
\end{tikzpicture}
\caption{One step of the four-child tree in the adversary of Kaplan,
Zamir, and Zwick~\cite[Section~5]{kzz}. An intermediate node records a
range of possible children. An item at $[1,3]$ can still enter any of
children $1$, $2$, or $3$.}
\label{fig:kzz-lattice}
\end{figure}

Their analysis measures the sorters progress in terms of a suitably defined potential, our analysis is similar, although more involved.
The resulting lower bound of this adversary is $\frac{37}{64}n\log n$ comparisons, improving the earlier
$\frac12 n\log n$ bound.