Q:

Minimum number of operation needed to sort a sequence of numbers in stack

We have N numbers in a stack and we want to sort them with minimum number of operations. The only available operation is reversing last K numbers in top of the stack (K can be between 2 and N).
For example to sort sequence "2 3 4 5 1", we need 2 steps:
2 3 4 5 1 ---> 1 5 4 3 2 ---> 1 2 3 4 5
Is there any polynomial algorithm to find minimum number of steps needed?

A:

I think you are talking about the famous Pancake sorting algorithm. 
Quoting from wikipedia : "The maximum number of flips required to sort 
any stack of n pancakes has been shown to lie between (15/14)n and (18/11)n,
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, and then take it down to its final 
position with  one more, then repeat this for the remaining pancakes.

Note that we do not count the time needed to find the largest pancake, only the
number of flips; if we wished to create a real machine to execute this algorithm
in linear time, it would have to both perform prefix reversal (flips) and be
able to find the maximum of a range of consecutive numbers in constant time"

