Pancake Sorting: How to Flip Less

How the game works

Tap a pancake to flip it and every pancake above it. Pointing at a pancake first shows which ones would move. The numbers on the pancakes are their sizes, 1 the smallest. Flipping just the top pancake changes nothing in the plain stacks, so a flip always lifts at least two there.

In this guide, "flip 3" means flip the top three pancakes, and a stack is written from the top down.

The simple method

Find the biggest pancake that is not yet in place. Flip it to the top, then flip it down to where it belongs. The bottom of the stack is then right and never needs touching again. Repeat with the next biggest.

That never takes more than two flips per pancake, and the last two pancakes need at most one, so any stack of n pancakes takes at most 2n − 3 flips. On the five-pancake stack it is already perfect.

Doing better

The simple method wastes flips when a pancake is already on top or when pancakes that belong together are scattered. The fewest flips usually come from building runs: pancakes next to their neighbour in size, in order or in reverse. A reversed run on top becomes an ordered run with one flip, so try to grow runs rather than placing one pancake at a time.

Every stack, solved

Four pancakes, 2 4 1 3, in four flips: flip 2 (4 2 1 3), flip 4 (3 1 2 4), flip 3 (2 1 3 4), flip 2 (1 2 3 4).

Five pancakes, 1 3 2 5 4, in five flips: flip 2 (3 1 2 5 4), flip 4 (5 2 1 3 4), flip 5 (4 3 1 2 5), flip 4 (2 1 3 4 5), flip 2 (1 2 3 4 5).

Six pancakes, 4 6 2 5 1 3, in seven flips, one fewer than the simple method: flip 2 (6 4 2 5 1 3), flip 3 (2 4 6 5 1 3), flip 4 (5 6 4 2 1 3), flip 2 (6 5 4 2 1 3), flip 6 (3 1 2 4 5 6), flip 3 (2 1 3 4 5 6), flip 2 (1 2 3 4 5 6).

Seven pancakes, 1 5 7 4 2 6 3, in eight flips: flip 2 (5 1 7 4 2 6 3), flip 3 (7 1 5 4 2 6 3), flip 7 (3 6 2 4 5 1 7), flip 3 (2 6 3 4 5 1 7), flip 5 (5 4 3 6 2 1 7), flip 3 (3 4 5 6 2 1 7), flip 4 (6 5 4 3 2 1 7), flip 6 (1 2 3 4 5 6 7).

Eight pancakes, 5 2 7 4 1 8 3 6, in nine flips: flip 2 (2 5 7 4 1 8 3 6), flip 4 (4 7 5 2 1 8 3 6), flip 6 (8 1 2 5 7 4 3 6), flip 8 (6 3 4 7 5 2 1 8), flip 4 (7 4 3 6 5 2 1 8), flip 3 (3 4 7 6 5 2 1 8), flip 5 (5 6 7 4 3 2 1 8), flip 3 (7 6 5 4 3 2 1 8), flip 7 (1 2 3 4 5 6 7 8). Notice how the last few flips build one long reversed run and then turn it over at once.

Burnt pancakes

Now each pancake has a burnt side, and every flip turns the lifted pancakes upside down. The stack is done when it is sorted with every burnt side facing down. Here a minus sign marks a pancake that is burnt side up, and you may flip the top pancake on its own.

A pancake turned over twice is back the way it started, so one that is burnt side up needs an odd number of flips and one that is burnt side down an even number.

Burnt pancakes, −1 −2 −3, already in order but every one burnt side up, in six flips: flip 2 (2 1 −3), flip 3 (3 −1 −2), flip 2 (1 −3 −2), flip 3 (2 3 −1), flip 2 (−3 −2 −1), flip 3 (1 2 3).

Four burnt pancakes, 2 1 −3 −4, in eight flips: flip 1 (−2 1 −3 −4), flip 3 (3 −1 2 −4), flip 4 (4 −2 1 −3), flip 3 (−1 2 −4 −3), flip 1 (1 2 −4 −3), flip 4 (3 4 −2 −1), flip 2 (−4 −3 −2 −1), flip 4 (1 2 3 4).

Where the puzzle comes from

The puzzle was published in 1975 by the mathematician Jacob Goodman under a playful pen name, and Bill Gates, then a student at Harvard, worked on it with his professor Christos Papadimitriou; their paper on how many flips a stack can need appeared in 1979. The exact worst case is still known only for fairly small stacks: any stack of six can be sorted in 7 flips, and any stack of eight in 9.