I've read in most places that the minimum number of flips in the worst case scenario required to sort a stack by any algorithm is between $15n/14$ and $18n/11$. But I read here:
It was shown in the mid-1990s that we can sort any permutation (stack
of unburnt pancakes) in $n-1$ reversals
that it's $n-1$. Is this wrong or have I misinterpreted the two results? Where can I see this 1990's paper which showed that it was $n-1$?
Best Answer
The article itself has your answer. "In the worst case, it will take between $15n/14$ and $18n/11$ flips to sort $n$ pancakes" by prefix reversals, but if you allow "sorting by reversals [of arbitrary substrings], rather than sorting by prefix reversals... we can sort any permutation (stack of unburnt pancakes) in $n-1$ reversals."
In pancake terms, when you pick up several pancakes at the top of the stack and flip them, you are performing a prefix reversal of the stack. But if have an extra plate, you can flip any contiguous section of pancakes in the middle the stack; you just slide the overlying pancakes off onto the other plate first, flip the pancakes you want, then slide the extra pancakes back on top. In other words, you can do an arbitrary (non-prefix) reversal.