# 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

## 1 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.

-
Thanks for opening my eyes into the world of reading things carefully before doubting it :) –  asymptotically Nov 10 '12 at 5:32