Pancake Sort

Problem Sort an array using ONLY a reverse(i) primitive that reverses the prefix [0..i] — no swaps or other mutations (pancake sorting).

Input / Output

• Input: int array. Output: the sequence of flips (or the sorted array).

Constraints

• n up to 100 classically; at most 2n flips expected — flip count, not comparisons, is the currency.

Example

• [3,2,4,1]: flip max 4 to front (reverse(2)) → [4,2,3,1], flip into place (reverse(3)) → [1,3,2,4]; continue with the prefix of size 3 → sorted with ≤ 2·4 flips.

Expected approach

• Selection-sort variant with prefix reversals: for size k = n down to 2, locate the maximum within the first k elements, reverse to bring it to index 0, then reverse(k−1) to sink it into its final slot; skip if already in place. ≤ 2 flips per element → O(n) flips, O(n^2) scans. Edge discipline: max already at front or already at position k−1. Trivia-level bonus: optimal pancake sorting is famously hard (the (15/14)n bound work) — the greedy 2n is what's expected.