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.

5 thoughts on “Pancakes Sorting Algorithm

  1. Actually, it would appear to me that this algorithm is linear time in number of pancakes. Again the complexity bound O(hλ) appears to be constant, but h is actually a linear function of number of pancakes, assuming they are of non-zero height l, it becomes:

    O(n*l*λ)

    n being the number of pancakes. Sorry man, it's still linear at best.

  2. Actually a friend pointed out to me that the algorithm is sub-linear. Acceleration on earth is nearly constant at 'a', the distance traveled after time 't' is

    d = .5 a*t^2

    to calculate the time it takes for pancake to fall from top of stack to, say in the worst case the bottom, is computed as a function of height of the stack H:

    t= sqrt(2H/a)

    so the time for the above algorithm is

    O(λ*sqrt(n*l)),

    Because l is a constant, the big-O of this pancake sorting algorithm comes to:

    O(λ*sqrt(n))

    which makes this a sub-linear algorithm for sorting pancakes.

  3. There is a problem with the induction step is that “λ” is not updated. Consider the following stack:

    4444
    333
    22
    666666

    prescribed cut is to happen 3 times after 2nd and 4th character (λ=6/2=3)

    44 44
    33 3
    22
    66 66 66

    when the fall happens in sub-linear time the resulting stack

    44
    33 44
    22 3
    66 66 66

    which is not sorted.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s