<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume8 Issue1" %>
Comparing Algorithms for Sorting with t Stacks in Series
Rebecca Smith
Department of Mathematics, University of Florida, Gainesville, FL 32611-8105, USA
Annals of Combinatorics 8 (1) p.113-121 March, 2004
AMS Subject Classification: 05A05, 68R05, 68W01
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.
Keywords: permutations, stack sorting, sorting in series


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.