Given a stack of pancakes, we assign each pancake a number , , where the pancakes are numbered in order of increasing diameter. 1 is the smallest pancake and is the largest. We assume that the pancakes have distinct diameters.
Our convention will be to describe a stack as a numeric list, with the leftmost element representing the current top of the stack. For example, denotes a stack of pancakes already sorted according to our preference: the smallest pancake is on top, directly beneath it lies the medium-sized pancake, and the largest pancake is at the bottom. is the opposite of our desired ordering: the pancakes are precariously stacked with the largest pancake on top.
Our goal is to sort the pancakes such that the largest pancake is on the bottom and every pancake has only smaller pancakes stacked above it. To achieve this goal, we have in our possession a powerful spatula, with which we can flip the entire stack or any topmost subsection. Our analysis will establish an upper bound on the number of flips required to sort a stack of pancakes, given an arbitrary initial ordering.
Establishing an Upper Bound
We will show that we can sort any stack of pancakes in at most flips.
For , the number of required flips is 0. For , the number of flips is at most 1.
Based on this, the obvious algorithm is to order pancakes 3 through at the bottom of the stack, then use at most 1 additional flip to order the top 2 pancakes.
In the for loop, the first flip brings pancake to the top of the stack and the second flip moves pancake to the th position in the stack. We see that, after the loop’s first iteration, pancake is at the bottom of the stack. The second iteration places pancake on top of pancake . Each additional iteration orders another pancake at the bottom of the stack. Thus, in at most 2 flips each, we sort the largest pancakes. Then, to sort pancakes and , we need at most one more flip. The total number of flips, using the obvious algorithm, is at most .
However, we can do better than this.
A Matlab program was written to generate all possible orderings of stacks of four pancakes, which correspond to the 24 permutations of the set . Then the above algorithm was run on each permutation, with the enhancement that unnecessary flips in the above routine were omitted. For example, with the permutation 2314, there is no need to waste two flips bringing 4 to the top of the stack (4132) and back to the bottom (2314). The results of the algorithm are presented in the following table:
Even using the obvious algorithm, we are able to sort almost any stack of 4 pancakes in 4 flips or less. Let us consider the two highlighted permutations which require, by the naive algorithm, 5 flips to sort. Treating these two permutations as special cases, it is possible to sort each of them in 3 flips: and . Thus, by incorporating the knowledge of how best to flip these two cases, we can extend our previous algorithm to sort the first pancakes using 2 flips each, and then sort the remaining 4 pancakes in, at most, 4 flips. This reduces our lower bound to . However, again we can do better.
Because it will help in the next stage of our analysis, we also note that the permutations 1243 and 1432, while requiring 4 flips by our basic algorithm, can each be sorted in 3 flips: and . We give the updated table below:
To further reduce our upper bound on the number of flips, we run our Matlab code on the 120 permutations of stacks of 5 pancakes. First, our basic algorithm (the psuedo-code above) is able to sort 97 of the stacks in 5 or fewer flips. This leaves us with 23 stacks that, potentially, require more than 5 flips to sort. These are presented below:
For each of the above permutations, we check to see if the number of flips required to bring pancake 5 to the bottom of the stack (which could be 0, 1, or 2 flips) plus the number of flips to sort the resulting permutation of (found via our table of results for ) on top of the stack was less than or equal to 5. In 14 cases, it was. This left us with 9 remaining permutations of five pancakes to consider.
A combination of brute-force search and table lookups of previous values produced the following solutions for each of the above 9 permutations, all in 5 flips or less:
Using an algorithm encoded with the special cases above, we can sort any stack of 5 pancakes in at most 5 flips. Thus, we extend our original algorithm to sort a stack of pancakes by first sorting the largest , using at most 2 flips each, followed by at most 5 flips to sort the last five pancakes. The total number of flips is less than or equal to flips, establishing our proposed upper bound.
Pancake Sorting on Wikipedia. Interestingly, Bill Gates coauthored a research paper on this sorting problem in 1979.