An Improved Lower Bound for Stack Sorting

MaRDI QIDQ6237733zbMATH OpenFDO

Authors Luke Schaeffer

Publication date 4 December 2012

Mathematics Subject Classification ID

Asymptotic enumeration (05A16)

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.561lo{g}_{2}n+O(1)$. This is the first significant improvement since the previous lower bound, $1/2lo{g}_{2}n+O(1)$, was established by Knuth in 1972.

This page was built for publication: An Improved Lower Bound for Stack Sorting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6237733)