The Pancake Sorting Problem

Description
I work as a waiter at a local breakfast establishment. The chef at the pancake house is sloppier than I like, and when I deliver the pancakes I want them to be sorted biggest on bottom and smallest on top. Problem is, all I have is a spatula. I can grab substacks of pancakes and flip them over to sort them, but I can't otherwise move them from the middle to the top.

How can I achieve this efficiently?

This is a well known problem called the pancake sorting problem. Bill Gates once wrote a paper on this that established the best known upper bound for 30 years.

This particular challenge is two-fold: implement the algorithm, and challenge one another for efficiency.

Input Description
You'll be given a pair of lines per input. The first line tells you how many numbers to read in the next line. The second line tells you the pancake sizes as unsigned integers. Read them in order and imagine them describing pancakes of given sizens from the top of the plate to the bottom. Example:

3
3 1 2
Output Description
Your program should emit the number of spatula flips it took to sort the pancakes from smallest to largest. Optionally show the intermediate steps. Remember, all you have is a spatula that can grab the pancakes from the 0th to the _n_th position and flip them. Example:

2 flips: 312 -> 213 -> 123
Challenge Input
8
7 6 4 2 6 7 8 7
----
8
11 5 12 3 10 3 2 5
----
10
3 12 8 12 4 7 10 3 8 10

Solution
in C++

Here's a simple algorithm that takes 2N flips. Since a flip is O(n) on average (reversing something about half the size of the entire stack) the entire runtime should be n2 ish. There are three insights:

1. We can move any item we like to the top of the stack with one flip.
2. We can move the top of the stack anywhere we like with one flip.
3. A flip never disturbs anything lower than where we're flipping from.
So we can use a recursive process where we find the largest pancake and move it to the bottom with two flips, then sort the remaining stack not including that largest one.


#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

namespace {

template<typename It>
void moveToEnd(It begin, It elem, It end) {
  std::reverse(begin, elem + 1);
  std::reverse(begin, end);
}

template<typename It>
void pancakeSort(It begin, It end) {
  if (begin == end) {
    return;
  }
  auto elem = std::max_element(begin, end);
  moveToEnd(begin, elem, end);
  pancakeSort(begin, end - 1);
}

}

int main() {
  int size;
  std::cin >> size;
  std::vector<int> stack(size);
  using It = std::istream_iterator<int>;
  std::copy(It(std::cin), It(), stack.begin());
  pancakeSort(stack.begin(), stack.end());
  std::cout << 2 * size << '\n';
}