xlvii. Pancake Sorting

Problem. Sort a stack by prefix reversals (flip the top $k$ pancakes).

Answer: at most $2n-3$ flips: bring the largest unsorted pancake to the top, then flip it into place. The exact minimum is NP-hard in general; known bounds are $\frac{15}{14}n\le$ worst case $\le \frac{18}{11}n$.

vector<int> pancakeSort(vector<int>& a) {         // returns flip lengths (reverse prefix of that length); at most 2n - 3 flips
    vector<int> flips; int n = sz(a);
    for (int len = n; len > 1; len--) {
        int m = max_element(a.begin(), a.begin() + len) - a.begin();
        if (m == len - 1) continue;
        if (m > 0) { reverse(a.begin(), a.begin() + m + 1); flips.push_back(m + 1); }
        reverse(a.begin(), a.begin() + len); flips.push_back(len);
    }
    return flips;
}

Proof: at most 2n − 3 flips

Each round places the largest of the first len elements at position len - 1 with at most two flips (one to bring it to the front, one to send it down), never touching positions already fixed. Rounds run for len $=n,\dots ,2$; when only two elements remain, a single flip suffices (if they are out of order, the maximum is at the front, so the first flip is skipped). So the total is at most $2(n-2)+1=2n-3$. Checked on random arrays, including the flip count. Burnt pancakes (each pancake must end burnt side down) need at most $2n$ flips by the same idea plus one orientation flip per round.