Sorting with a popqueue (Q6551807)

In this work, the authors consider a new data structure for sorting permutations, which they call popqueue in analogy with a much older notion called the popstack. They consider two sorting algorithms on popqueues, \texttt{Min} and \texttt{Cons}. They first classify permutations which are sorted by these algorithms in one pass. They then consider sorting in two passes and show that \texttt{Cons} is a more natural sorting algorithm. The authors classify permutations that are sortable by \texttt{Cons} in terms of pattern avoidance. They end with determining possible outputs of \texttt{Cons}, permutations with sort to them, and enumeration questions.