Pancakes Sorting Algorithm

There is a recent Slashdot article about pancake sorting. Somebody seem to have proved that optimal sorting of pancakes is NP-hard. If you look at the citations in the paper[arxiv], you'll notice the mentioning of a paper by a certain "W. Gates"... the by the very same Bill Gates that everybody knows about.

I mentioned the problem to my father, and he, having a Ph.D. in mathematics came up with the operational gadgetry to perform comparison on any two pancakes, and declared the problem done. Later on he called me and told me to use this problem to attract a date to bed.... sigh.... Btw, his gadget for comparing two pancakes uses only two flips, mine used three. sigh....

So during our latter discussion, as he gave me this great idea, we also chance upon another interesting solution to the sorting problem, which has complexity

O(hλ)

where h is the height of the stack and λ condition number:the ratio of the largest pancake to the smallest pancake in the stack. How? Consider this algorithm:

* Flip the stack side ways so one side of all pancakes are flush
* Flip back upright.
* Cut from flush side λ cuts starting from the flush side towards the non-flush side. The widths of all cut is to be equal. That width can be any width smaller than the width of the smallest pancake. To achieve fewest cut we use the width of the smallest pancake.
* The pieces of pancakes will fall, producing a stack of pancakes including all sizes of original sizes with the largest at the bottom and the smallest at the top.

It takes a small bit of animation skill, which the blogger does not have, to illustrate it. Or if you can just imagine for me.  The rate at which object fall is roughly proportional to the height from which it falls. Since we are on earth, and there is a terminal velocity, the time it will take for all pieces of pancake to fall into place after each cut is height divided by terminal velocity--so linear in height of the stack. since there are λ cuts, the algorithm takes O(hλ) to run. The proof will be in the pudding after breakfast by induction:

Base case: We start with one pancake. Slice laser down at any width less than this pancake's width.The pieces fall to no where and the pancake is now sorted.

Induction Hypothesis: suppose we can sort in n-1 pancakes using the above algorithm using λ laser slices,

Induction Step: W.L.O.G. add one pancake on top of the n-1 stack to create a stack of size n: Suppose the newly added pancake is smaller than the smallest pancake in the existing stack of size n-1. then the problem is solved: Slicing from it's right side keeps it on top, and since new slicing width is same as lower stack's slicing width, using this width to continue slicing will sort the stack of n-1 pancakes below as well.

Suppose the top nth pancake is not the smallest slice in the n-1 stack, let us use the smallest slice width from n-1 stack. By slicing the top pancake by that width creates a new pancake of the smallest size. The remaining portion of the top pancake in the n stack falls down and becomes part of a pancake in an n stack. Note that this operation has swapped the position of the lowest pancake in n-1 stack taking on the smallest size with the top pancake from n stack. Smallest pancake is on top, and we have a stack of n-1 unsorted pancakes. We can proceed using the current width and sort the remaining n-1 pancakes by I.H. in O((h-1)λn) time. Adding the one cut from this step yields a total of O(hλn) running time.

Q.E.D!

Rule of physics challenge: okay, so the pancake may fall out of order from the torque exerted by gravity as it receives support from only one side. This issue may be mitigated if we set up λ lasers in λ time and perform all of the the slicing simultaneously, thus all pieces fall vertically, solving the torque problem.

Btw, if we do not know lambda, then clearly it takes O(n) time to compute it using the comparison gadget. in that case we have  

O(hλ+2n)

 running time. Linear time is still superior to  O(nlg(n)) using only pair-wise comparisons and swaps.