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 QS\mathbb{Q}_{\Sigma} is the shuffle queue corresponding to the shuffling method S\Sigma, then we find a number of surprising results related to two natural variations of shuffle queues denoted by Q'S\mathbb{Q}_{\Sigma}^{\prime} and QpopS\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 Q'cuts\mathbb{Q}_{\text{cuts}}^{\prime} is the set of the 321321-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 nn-permutations, pn(Q'S)p_{n}(\mathbb{Q}_{\Sigma}^{\prime}), that one can sort by using Q'S\mathbb{Q}_{\Sigma}^{\prime}, for any shuffling method S\Sigma, corresponding to a set of irreducible permutations.We also show that pn(QpopS)p_{n}(\mathbb{Q}_{\Sigma}^{\textsf{pop}}) is given by the odd indexed Fibonacci numbers F2n-1F_{2n-1}, for any shuffling method S\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 QpopIn-sh\mathbb{Q}_{\text{In-sh}}^{\textsf{pop}} and QpopMonge\mathbb{Q}_{\text{Monge}}^{\textsf{pop}}, corresponding to the popular \emph{In-shuffle} and \emph{Monge} shuffling methods.