[22/O46] Sorting by stacks. The input is a permutation of n integers. These integers, one at a time, pass through a sequence of m first-in-last-out stacks S1,...,Sm, from S1 to Sm. If an integer k is to be pushed on Si, then this stack can pop some integers from the top down, pushing them on Si+1 in that order, before pushing k into Si.

The output sequence from Sm gives the final permutation.

(a) Show that we can sort integers with log n stacks.

(b) Use the incompressibility method to show that 1 2 log n stacks are needed on average.

(c) Open: Close the gap between Item

(a) and (b).

Comments. The problem was investigated by R.E. Tarjan [J. Assoc.

Comp. Mach., 19(1972), 341–346] and D.E. Knuth [The Art of Computer Programming, Vol. 3: Sorting and Searching, 1998 (2nd edition), Section 5.2.4, Exercises 19 and 20]. Item (b), and related studies such as sorting with parallel stacks and queues, can be found in [T. Jiang, M. Li and P.M.B. Vit´anyi, J. Comput. Sci. Tech., 15:5(2000), 402–408].