Sorting by Shuffling Methods and a Queue

Abstract

We study sorting by queues that can rearrange their content by applying permutations from a predefined set. These new sorting devices are called shuffle queues and we investigate those of them corresponding to sets of permutations defining some well-known shuffling methods. If $\mathbb{Q}_{\Sigma}$ is the shuffle queue corresponding to the shuffling method $\Sigma$, then we find a number of surprising results related to two natural variations of shuffle queues denoted by $\mathbb{Q}_{\Sigma}^{\prime}$ and $\mathbb{Q}_{\Sigma}^{\textsf{pop}}$. These require the entire content of the device to be unloaded after a permutation is applied or unloaded by each pop operation, respectively.

First, we show that sorting by a deque is equivalent to sorting by a shuffle queue that can reverse its content. Next, we focus on sorting by cuts. We prove that the set of permutations that one can sort by using $\mathbb{Q}_{\text{cuts}}^{\prime}$ is the set of the $321$-avoiding separable permutations. We give lower and upper bounds to the maximum number of times the device must be used to sort a permutation. Furthermore, we give a formula for the number of $n$-permutations, $p_{n}(\mathbb{Q}_{\Sigma}^{\prime})$, that one can sort by using $\mathbb{Q}_{\Sigma}^{\prime}$, for any shuffling method $\Sigma$, corresponding to a set of irreducible permutations.

We also show that $p_{n}(\mathbb{Q}_{\Sigma}^{\textsf{pop}})$ is given by the odd indexed Fibonacci numbers $F_{2n-1}$, for any shuffling method $\Sigma$ having a specific \say{back-front} property. The rest of the work is dedicated to a surprising conjecture inspired by Diaconis and Graham, which states that one can sort the same number of permutations of any given size by using the devices $\mathbb{Q}_{\text{In-sh}}^{\textsf{pop}}$ and $\mathbb{Q}_{\text{Monge}}^{\textsf{pop}}$, corresponding to the popular \emph{In-shuffle} and \emph{Monge} shuffling methods.