<%@ 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
smithr@math.ufl.edu
Annals of Combinatorics 8 (1) p.113-121 March, 2004
AMS Subject Classification: 05A05, 68R05, 68W01
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.
Keywords: permutations, stack sorting, sorting in series

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.