Computational progress on sorting with stacks in series

# Computational progress on sorting with stacks in series

<br />

**[Vince Vatter](https://vincevatter.com/)** (University of Florida)

joint with **[Jay Pantone](https://jaypantone.com/)** (Marquette University)

<br />

***

August 7, 2026

MAA MathFest, Boston

***

---

# Sorting with stacks in series

Organized by the number of stacks:

Part 1: **stack** — complete structural and enumerative understanding.

Part 2: **stacks** — polynomial-time recognition, but no comparably satisfying structural explanation.

Part 3: **stacks** — a computational frontier that is rapidly narrowing.

---

# Part 1: stack

---

# A stack as a railway

<figure class="taocp-railway-figure">
  <img src="fig-taocp-1-stack.png?v=20260803-contrast-1" alt="Knuth's illustration of a stack as a railway switching network, with input and output tracks meeting a stack siding">
  <figcaption>Donald E. Knuth, <em>The Art of Computer Programming</em>, Vol. 1: <em>Fundamental Algorithms</em>, 3rd ed., p. 240 (Addison-Wesley, 1997).</figcaption>
</figure>

---

# The machine

Input enters on the right; only the **top** of the stack can move. Goal: output $1, 2, \ldots, n$.

---

# The stack-sorting algorithm

<div class="algorithm-rules">
  <div class="algorithm-rule">
    <span class="algorithm-action">PUSH</span>
    <span>if input remains and either the stack is empty or next input $<$ top</span>
  </div>
  <div class="algorithm-rule">
    <span class="algorithm-action">POP</span>
    <span>otherwise</span>
  </div>
</div>

<div class="algorithm-stop">Stop when the input and stack are both empty.</div>

<div class="algorithm-takeaway"><strong>If $\pi$ can be sorted with one stack, this deterministic algorithm sorts it.</strong></div>

---

# When the algorithm fails

The same rule, now applied to $\pi = 6\,1\,5\,2\,4\,3\,8\,9\,7$.

---

# The issue is $231$

In the failed example, $8,9,7$ occur in the relative order $2,3,1$.

A permutation *contains* the pattern $231$ if three of its entries occur in the same relative order as $231$.

Deleting entries from a sortable permutation leaves a sortable permutation.

<br />

**Theorem (Knuth).**
_$\pi$ is one-stack sortable if and only if it contains no $231$ pattern._

Every failure is caused by this one three-entry obstruction.

<figure class="taocp-figure">
  <img src="fig-taocp-1-stack-exercises.png?v=20260803-contrast-1" alt="Two TAOCP exercises asking for the enumeration and pattern characterization of permutations obtainable with one stack">
  <figcaption>Donald E. Knuth, <em>The Art of Computer Programming</em>, Vol. 1: <em>Fundamental Algorithms</em>, 3rd ed., §2.2.1, Exercises 4–5 (Addison-Wesley, 1997).</figcaption>
</figure>

---

# A bijection with stack words

Record the deterministic algorithm by writing $P$ for each **push** and $O$ for each **pop**.

A stack word is **valid** when it has

- $n$ copies of $P$ and $n$ copies of $O$, and
- at least as many $P$'s as $O$'s in every prefix.

**This encoding is a bijection:**

<div class="stack-word-bijection" role="img" aria-label="Bijection between sortable permutations of length n and valid stack words of semilength n">
  <div class="stack-word-side">
    <strong>sortable permutations</strong>
    <span>of length $n$</span>
  </div>
  <div class="stack-word-arrow" aria-hidden="true">↔</div>
  <div class="stack-word-side">
    <strong>valid stack words</strong>
    <span>of semilength $n$</span>
  </div>
</div>

Valid stack words are Dyck words, so both sets are counted by the Catalan numbers:

$$
C\_n = \frac{1}{n+1}\binom{2n}{n}.
$$

For one stack, the machine, the forbidden pattern, and the enumeration all fit together. This coherence disappears with two stacks.

---

# Part 2: stacks

---

# Two stacks in series

---

# Basis

<p class="basis-theorem"><strong>Theorem (Murphy, 2002).</strong> <i>There are infinitely many minimal non-two-stack-sortable permutations.</i></p>

<div class="basis-figure-pair">
  <figure class="basis-infinite-figure">
    <img src="fig-murphy-infinite-basis-p-316.png?v=20260803-contrast-1" alt="Murphy's proposition giving an infinite family of basis elements for permutations sortable by two stacks in series">
    <figcaption>Murphy, <a href="http://hdl.handle.net/10023/11023"><i>Restricted Permutations, Antichains, Atomic Classes, and Stack Sorting</i></a><br><span class="murphy-citation-details">PhD thesis, University of St Andrews (2002), p. 316.</span></figcaption>
  </figure>
  <figure class="basis-infinite-figure">
    <img src="fig-murphy-infinite-basis-p-319.png?v=20260803-contrast-1" alt="Murphy's diagram showing one member of the infinite family as a basis element for two-stack sortability">
    <figcaption>Murphy, <a href="http://hdl.handle.net/10023/11023"><i>Restricted Permutations, Antichains, Atomic Classes, and Stack Sorting</i></a><br><span class="murphy-citation-details">PhD thesis, University of St Andrews (2002), p. 319.</span></figcaption>
  </figure>
</div>

---

<figure class="basis-list-figure">
  <img src="fig-murphy-2ss-basis-p-303.png?v=20260803-contrast-1" alt="Murphy's table of the short basis elements for permutations sortable by two stacks in series">
  <figcaption>Murphy, <a href="http://hdl.handle.net/10023/11023"><i>Restricted Permutations, Antichains, Atomic Classes, and Stack Sorting</i></a><br><span class="murphy-citation-details">PhD thesis, University of St Andrews (2002), p. 303.</span></figcaption>
</figure>

---

# Recognition problem

Given a permutation $\pi$ of length $n$, determine whether it can be sorted by two stacks in series.

<br />

**[Atkinson, Murphy, and Ruškuc (2002)](https://doi.org/10.1016/S0304-3975%2801%2900270-5):** conjectured **NP-complete**.

**[Murphy (2002)](http://hdl.handle.net/10023/11023):** conjectured **P**.

**[Pierrot and Rossin (2013)](https://arxiv.org/abs/1303.4376) and [Pierrot and Rossin (2017)](https://doi.org/10.1007/s00224-016-9743-8):** it is in **P**.

---

# A Boolean encoding

<div class="relation-definitions" aria-label="Definitions of the L and R cohabitation relations">
  <div class="relation-definition relation-definition-l"><span class="relation-symbol"><i>L</i>(<i>x</i>,<i>y</i>)</span>: <i>x</i> and <i>y</i> share the output-side stack.</div>
  <div class="relation-definition relation-definition-r"><span class="relation-symbol"><i>R</i>(<i>x</i>,<i>y</i>)</span>: <i>x</i> and <i>y</i> share the input-side stack.</div>
</div>

---

# Compatibility, coupling, and transitivity

<div class="constraint-system">
  <section class="constraint-row">
    <div class="constraint-heading">Compatibility<span class="constraint-cnf">2-CNF</span></div>
    <div class="constraint-content constraint-compatibility">
      <div class="constraint-form">
        <span class="constraint-domain">noninversion</span>
        <span class="constraint-math">$\textcolor{#b52f40}{R(x,y)} \Longleftrightarrow \textcolor{#1268bd}{L(x,y)}$</span>
      </div>
      <div class="constraint-form">
        <span class="constraint-domain">inversion</span>
        <span class="constraint-math">$\textcolor{#b52f40}{R(x,y)} \Longleftrightarrow \neg \textcolor{#1268bd}{L(x,y)}$</span>
      </div>
    </div>
  </section>

<section class="constraint-row">
    <div class="constraint-heading">Coupling<span class="constraint-cnf">2-CNF</span></div>
    <div class="constraint-content constraint-paired-forms">
      <div class="constraint-form constraint-form-l">
        <span class="constraint-domain">for values <i>x</i> < <i>y</i> < <i>z</i></span>
        <span class="constraint-math">$\textcolor{#1268bd}{L(x,z)} \implies \textcolor{#1268bd}{L(y,z)}$</span>
      </div>
      <div class="constraint-form constraint-form-r">
        <span class="constraint-domain">for positions <i>i</i> < <i>j</i> < <i>k</i></span>
        <span class="constraint-math">$\textcolor{#b52f40}{R(\pi(i),\pi(k))} \implies \textcolor{#b52f40}{R(\pi(i),\pi(j))}$</span>
      </div>
    </div>
  </section>

<section class="constraint-row">
    <div class="constraint-heading">Transitivity<span class="constraint-cnf">3-CNF</span></div>
    <div class="constraint-content constraint-paired-forms">
      <div class="constraint-form constraint-form-l">
        <span class="constraint-domain">for values <i>x</i> < <i>y</i> < <i>z</i></span>
        <span class="constraint-math">$\textcolor{#1268bd}{L(x,y)} \wedge \textcolor{#1268bd}{L(y,z)} \implies \textcolor{#1268bd}{L(x,z)}$</span>
      </div>
      <div class="constraint-form constraint-form-r">
        <span class="constraint-domain">for positions <i>i</i> < <i>j</i> < <i>k</i></span>
        <span class="constraint-math">$\textcolor{#b52f40}{R(\pi(i),\pi(j))} \wedge \textcolor{#b52f40}{R(\pi(j),\pi(k))} \implies \textcolor{#b52f40}{R(\pi(i),\pi(k))}$</span>
      </div>
    </div>
  </section>
</div>

<div class="constraint-consequence"><i>Every sortable $\pi$ admits an encoding satisfying all three conditions.</i></div>

---

# The exact formula, and Murphy's conjecture

<p class="murphy-statement"><strong>Theorem (Murphy, 2002).</strong> <i>The converse holds: if $\pi$ admits an encoding satisfying compatibility, coupling, and transitivity, then $\pi$ is sortable.</i></p>

<p class="murphy-statement"><strong>Conjecture (Murphy, 2002).</strong> <i>Transitivity is unnecessary: compatibility and coupling alone characterize two-stack sortability.</i></p>

---

<figure class="murphy-quote-figure">
  <img src="fig-murphy-conjecture-tested-p-323-324.png?v=20260803-contrast-1" alt="Excerpt from Murphy's thesis explaining that the conjecture was tested by hand for permutations of length 18 and less">
  <figcaption>Murphy, <a href="http://hdl.handle.net/10023/11023"><i>Restricted Permutations, Antichains, Atomic Classes, and Stack Sorting</i></a><br><span class="murphy-citation-details">PhD thesis, University of St Andrews (2002), pp. 323–324.</span></figcaption>
</figure>

---

# The conjecture is false

<p class="counterexample-result"><strong>Pantone and V (2026).</strong> <i>The conjecture is false.</i></p>

<p class="counterexample-conclusion">These fourteen permutations satisfy $CC$ but are not sortable by two stacks in series.</p>

---

# Murphy's criterion is exact when $\pi$ ends in $1$

<p class="ending-one-theorem"><strong>Theorem (Pantone and V, 2026).</strong> <i>If $\pi$ ends in $1$, then $\pi$ is sortable by two stacks in series if and only if $CC(\pi)$ is satisfiable.</i></p>

<div class="ending-one-work"><strong>Ongoing work.</strong> Turn this into a polynomial-time algorithm for determining two-stack sortability.</div>

---

# Interlude

<figure class="knuth-open-problem-figure">
  <img src="fig-taocp-3-p-168.png?v=20260803-contrast-1" alt="Knuth's open problem asking for the growth rate of the number of stacks needed to produce all permutations">
  <figcaption>Donald E. Knuth, <em>The Art of Computer Programming</em>, Vol. 3: <em>Sorting and Searching</em>, 2nd ed., p. 168 (Addison-Wesley, 1998).</figcaption>
</figure>

<p class="interlude-bound">To sort all permutations of length $N$, we need between $\log_4 N$ and $\log_2 N$ stacks.</p>

<p class="interlude-question">What is the true rate of growth?</p>

---

# Part 3: stacks

---

# Three stacks in action

---

# The bet 🍺

<figure class="wager-figure">
  <img src="fig-elder-waton-wager.png?v=20260803-contrast-1" alt="Elder and Vatter's 2005 problem list recounting Murray Elder and Steve Waton's wager on the shortest permutation not sortable by three stacks in series">
  <figcaption>Elder and Vatter, <a href="https://arxiv.org/abs/math/0505504"><i>Problems and Conjectures presented at the Third International Conference on Permutation Patterns</i></a><br><span class="wager-citation-details">arXiv:math/0505504 (2005).</span></figcaption>
</figure>

Historical upper bounds:

- **[Tarjan (1972)](https://doi.org/10.1145/321694.321704)** reported an obstruction of length $41$.
- **[Atkinson (1992)](https://carleton.ca/scs/?p=15050)**, in an unpublished technical report, exhibited one of length $38$ — the shortest known for nearly thirty-five years.

---

# The search

<p class="search-theorem"><strong>Theorem (<a href="https://carleton.ca/scs/?p=15050">Atkinson, 1992</a>).</strong> <i>For every $t$, every shortest permutation that is not sortable by $t$ stacks in series ends in $1$.</i></p>

<p class="search-attribution"><strong>Pantone and V (2026).</strong> We attack the remaining search in two complementary directions.</p>

<ol class="search-directions">
  <li><strong>Prove sortability.</strong> There are far too many permutations to brute-force, so we use constructions of sortable permutations.</li>
  <li><strong>Hunt obstructions.</strong> Hill climbing, simulated annealing, and related methods propose candidates; an exact SAT formulation determines whether each is sortable by three stacks in series.</li>
</ol>

---

# The length-$21$ obstruction

<p class="obstruction-result"><strong>Pantone and V (2026).</strong> Our searches have found <strong>7,354</strong> minimal permutations of length $22$ that are not sortable by three stacks in series.</p>

<p class="obstruction-result">At length $21$, however, we have found <strong>one—and only one</strong>.</p>

<div class="obstruction-plot-wrap">
<svg class="obstruction-plot" viewBox="0 0 560 560" role="img" aria-labelledby="obstruction-plot-title obstruction-plot-desc">
  <title id="obstruction-plot-title">The length-21 permutation plotted as a function</title>
  <desc id="obstruction-plot-desc">Twenty-one dots on a twenty-one by twenty-one grid, at i comma pi of i for the permutation 6, 3, 12, 8, 17, 5, 2, 11, 7, 19, 14, 10, 4, 18, 13, 21, 16, 9, 20, 15, 1.</desc>

---

# Both Elder and Waton were wrong

<p class="bet-results-question"><i>What is the shortest permutation that cannot be sorted by a general $3$-stack sorting machine?</i></p>

- **Elder's $15$ is too small.** Every permutation of length $16$ or less is sortable.
- **Waton's $22$ is too large.** Not every permutation of length $21$ is sortable.

<p class="bet-results-verdict">Neither gets a 🍺.</p>

<div class="remaining-lengths">
  <p>Only four lengths remain to be resolved:</p>
  <div>$17,\ 18,\ 19,\ 20$</div>
</div>

<div class="thank-you-reveal">Thank you</div>