  We consider the problem of comparison-sorting an $n$-permutation $S$ that
avoids some $k$-permutation $\pi$. Chalermsook, Goswami, Kozma, Mehlhorn, and
Saranurak prove that when $S$ is sorted by inserting the elements into the
GreedyFuture binary search tree, the running time is linear in the extremal
function $\mathrm{Ex}(P_\pi\otimes \text{hat},n)$. This is the maximum number
of 1s in an $n\times n$ 0-1 matrix avoiding $P_\pi \otimes \text{hat}$, where
$P_\pi$ is the $k\times k$ permutation matrix of $\pi$, $\otimes$ the Kronecker
product, and $\text{hat} =
\left(\begin{array}{ccc}&\bullet&\\\bullet&&\bullet\end{array}\right)$. The
same time bound can be achieved by sorting $S$ with Kozma and Saranurak's
SmoothHeap.
  In this paper we give nearly tight upper and lower bounds on the density of
$P_\pi\otimes\text{hat}$-free matrices in terms of the inverse-Ackermann
function $\alpha(n)$. \[ \mathrm{Ex}(P_\pi\otimes \text{hat},n) =
\left\{\begin{array}{ll} \Omega(n\cdot 2^{\alpha(n)}), & \mbox{for most
$\pi$,}\\ O(n\cdot 2^{O(k^2)+(1+o(1))\alpha(n)}), & \mbox{for all $\pi$.}
\end{array}\right. \] As a consequence, sorting $\pi$-free sequences can be
performed in $O(n2^{(1+o(1))\alpha(n)})$ time. For many corollaries of the
dynamic optimality conjecture, the best analysis uses forbidden 0-1 matrix
theory. Our analysis may be useful in analyzing other classes of access
sequences on binary search trees.
