Sorting by shuffling methods and a queue (Q2161211)

Summary: 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}^{\mathsf{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}^\prime_{\text{cuts}}\) 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}^\prime_{\Sigma})\), that one can sort by using \(\mathbb{Q}^\prime_{\Sigma}\), for any shuffling method \(\Sigma\), corresponding to a set of irreducible permutations. We also show that \(p_n(\mathbb{Q}_{\Sigma}^{\mathsf{pop}})\) is given by the odd indexed Fibonacci numbers \(F_{2n-1}\), for any shuffling method \(\Sigma\) having a specific ``back-front'' property. The rest of the work is dedicated to a surprising conjecture inspired by \textit{P. Diaconis} and \textit{R. Graham} [Magical mathematics. The mathematical ideas that animate great magic tricks. With a foreword by Martin Gardner. Reprint of the 2012 hardback edition. Princeton, NJ: Princeton University Press (2015; Zbl 1323.00007)], which states that one can sort the same number of permutations of any given size by using the devices \(\mathbb{Q}_{\text{In-sh}}^{\mathsf{pop}}\) and \(\mathbb{Q}_{\text{Monge}}^{\mathsf{pop}}\), corresponding to the popular In-shuffle and Monge shuffling methods.