The Order of the (123, 132)-Avoiding Stack Sort

Abstract

Let $s$ be West's deterministic stack-sorting map. A well-known result (West) is that any length $n$ permutation can be sorted with $n-1$ iterations of $s.$ In 2020, Defant introduced the notion of highly-sorted permutations -- permutations in $s^t(S_n)$ for $t⪅n-1.$ In 2023, Choi and Choi extended this notion to generalized stack-sorting maps $s_{\sigma },$ where we relax the condition of becoming sorted to the analogous condition of becoming periodic with respect to $s_{\sigma }.$ In this work, we introduce the notion of minimally-sorted permutations ${\mathfrak{M}}_n$ as an antithesis to Defant's highly-sorted permutations, and show that ${\text{ord}}_{s_{123,132}}(S_n)=2\lfloor \frac{n-1}{2}\rfloor ,$ strengthening Berlow's 2021 classification of periodic points.