How Many Pop-Stacks Does It Take To Sort A Permutation?
Michael Albert, Vincent R. Vatter · The Computer Journal · 2021
Abstract Pop-stacks are variants of stacks that were introduced by Avis and Newborn in 1981. Coincidentally, a 1982 result of Unger implies that every permutation of length $n$ can be sorted by $n-1$ passes through a deterministic pop-stack. We give a new proof of this result inspired by Knuth’s zero-one principle.