An Improved Lower Bound for Stack Sorting

Abstract

We consider the problem of sorting elements on a series of stacks, introduced by Tarjan and Knuth. We improve the asymptotic lower bound for the number of stacks necessary to sort $n$ elements to $0.561{\log }_{2}n+O(1)$. This is the first significant improvement since the previous lower bound, $1/2{\log }_{2}n+O(1)$, was established by Knuth in 1972.

11 pages, 1 figure