Comparing Algorithms for Sorting with
*t* Stacks in Series

Rebecca Smith

Department of Mathematics, University of Florida, Gainesville, FL 32611-8105, USA

smithr@math.ufl.edu

Annals of Combinatorics 8 (1) p.113-121 March, 2004

Abstract:

We show that the left-greedy
algorithm is a better algorithm than the right-greedy algorithm
for sorting permutations using *t* stacks in series when *t* > 1.
We also supply a method for constructing some permutations that
can be sorted by *t* stacks in series and from this get a lower
bound on the number of permutations of length *n* that are
sortable by *t* stacks in series.
Finally we show that the left-greedy algorithm is neither optimal nor
defines a closed class of permutations for *t* > 2.

References:

1. M.D. Atkinson, M.M. Murphy, and N. Ruškuc, Sorting with two ordered stacks in series, Theoret. Comput. Sci. 289 (2002) 205–223.

2. M. Bóna, Combinatorics of Permutations, C.R.C. Press, 2004.

3. M. Bóna, A survey of stack sorting disciplines, Elect. J. Combin. 9 (2) (2002–2003) #A1.

4. D.E. Knuth, Fundamental Algorithms, The Art of Computer Programming, Vol. 1, 2nd Ed., Addison-Wesley, Reading, MA 1973, World Scientific, 2002.

5. J. West, Sorting twice through a stack, Theoret. Comput. Sci. 117 (1993) 303–313.