Comparing algorithms for sorting with \(t\) stacks in series (Q1889895): Difference between revisions

Consider a series of stacks and an input permutation of \(\{1,\dots,n\}\) on the far right. In one move we can remove the first element from the input and push it to the rightmost stack, or pop an element from a non-empty stack and push it to the stack to its left, or pop an element from the leftmost stack and append it to the output permutation on the far left. Such a move is legal if all non-empty stacks remain sorted with the least element on top. For each permutation \(p\) exists a \(t\) such that \(p\) can be sorted by \(t\) stacks in series. \textit{M. Bóna} [Electron. J. Comb. 9, Research paper A1 (2003; Zbl 1028.05003)] gives a survey of stack sorting. A permutation that can be sorted by the right-greedy algorithm can be sorted by the left-greedy algorithm using the same number of stacks. At least \(t!(t+1)^{n-t}\) permutations of \(\{1,\dots,n\}\) can be sorted by the left-greedy algorithm using \(t\) stacks. This algorithm is not optimal. It does not define a closed class of permutations for \(t>2\).