On average and highest number of flips in pancake sorting

AbstractWe are given a stack of pancakes of different sizes and the only allowed operation is to take several pancakes from the top and flip them. The unburnt version requires the pancakes to be sorted by their sizes at the end, while in the burnt version they additionally need to be oriented burnt-side down. We are interested in the largest value of the number of flips needed to sort a stack of n pancakes, both in the unburnt version (f(n)) and in the burnt version (g(n)).We present exact values of f(n) up to n=19 and of g(n) up to n=17 and disprove a conjecture of Cohen and Blum by showing that the burnt stack −I15 is not the hardest to sort for n=15.We also show that sorting a random stack of n unburnt pancakes can be done with at most 17n/12+O(1) flips on average. The average number of flips of the optimal algorithm for sorting stacks of n burnt pancakes is shown to be between n+Ω(n/logn) and 7n/4+O(1) and we conjecture that it is n+Θ(n/logn).Finally we show that sorting the stack −In needs at least ⌊(3n+3)/2⌋ flips, which slightly increases the lower bound on g(n). This bound together with the upper bound for sorting −In found by Heydari and Sudborough in 1997 [10] gives the exact number of flips to sort it for n≡3(mod4) and n≥15