# Pancake Sort in (n-1) flips

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$?

-
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." – Rahul Nov 8 '12 at 1:31
@RahulNarain Oops, didn't read that too carefully. So that's if you reverse any contiguous section in the stack? – asymptotically Nov 8 '12 at 1:43
Yes, that's what "sliding a batch of pancakes... onto the spare plate" allows you to do: you can now reach a contiguous section arbitrarily deep into the stack and reverse it. Hang on, I should post a proper answer. – Rahul Nov 10 '12 at 2:18

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."