Pancake sorting

Pancake sorting is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number is the minimum number of flips required for a given number of pancakes. In this form, the problem was first discussed by American geometer Jacob E. Goodman. It is a variation of the sorting problem in which the only allowed operation is to reverse the elements of some prefix of the sequence. Unlike a traditional sorting algorithm, which attempts to sort with the fewest comparisons possible, the goal is to sort the sequence in as few reversals as possible. A variant of the problem is concerned with burnt pancakes, where each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on bottom.

The minimum number of flips required to sort any stack of n pancakes has been shown to lie between 15/14n and 18/11n (approximately 1.07n and 1.64n,) but the exact value is not known.

The simplest pancake sorting algorithm requires at most 2n − 3 flips. In this algorithm, a variation of selection sort, we bring the largest pancake not yet sorted to the top with one flip; take it down to its final position with one more flip; and repeat this process for the remaining pancakes.

In 1979, Bill Gates and Christos Papadimitriou gave an upper bound of 5/3n. This was improved, thirty years later, to 18/11n by a team of researchers at the University of Texas at Dallas, led by Founders Professor Hal Sudborough (Chitturi et al., 2009).

...
Wikipedia