# Pancake Sort

# Pancake Sort

Pancake sort orders a sequence using only prefix reversals. A flip operation reverses the first $k$ elements of the array. By applying a sequence of flips, the algorithm moves the largest remaining element to its correct position at the end.

The model comes from sorting pancakes with a spatula, where only prefix flips are allowed.

## Problem

Given a sequence $A$ of length $n$, reorder it such that

$$
A[0] \le A[1] \le \cdots \le A[n-1]
$$

using only prefix reversals.

## Operation

A flip of size $k$ performs:

$$
[A_0, A_1, \dots, A_{k-1}] ;\rightarrow; [A_{k-1}, \dots, A_1, A_0]
$$

## Algorithm

For each position from the end toward the beginning:

1. Find the maximum element in the unsorted prefix
2. Flip it to the front
3. Flip it to its correct final position

```id="k9x3p1"
pancake_sort(A):
    n = length(A)

    for curr_size from n down to 2:
        max_index = index of max(A[0..curr_size-1])

        if max_index != curr_size - 1:
            flip(A, max_index + 1)
            flip(A, curr_size)
```

## Example

Let

$$
A = [3, 6, 1, 5, 2, 4]
$$

Step 1:

Max = 6 at index 1
Flip first 2 → [6,3,1,5,2,4]
Flip first 6 → [4,2,5,1,3,6]

Step 2:

Max = 5 in remaining
Repeat flips:

Final result:

$$
[1,2,3,4,5,6]
$$

## Correctness

Each iteration places the largest remaining element at its final position. Prefix reversals preserve the relative structure of the remaining elements. After processing all positions, the array becomes sorted.

## Complexity

| case    | time     |
| ------- | -------- |
| best    | $O(n^2)$ |
| worst   | $O(n^2)$ |
| average | $O(n^2)$ |

Each step requires scanning and up to two flips.

Space complexity:

$$
O(1)
$$

## Properties

* in-place
* not stable
* restricted to prefix reversals
* interesting theoretical model

## When to Use

Pancake sort is mainly of theoretical and educational interest. It appears in problems involving restricted operations, such as sorting with limited moves.

## Implementation

```id="m2x8q4"
def flip(a, k):
    a[:k] = reversed(a[:k])

def pancake_sort(a):
    n = len(a)

    for curr_size in range(n, 1, -1):
        max_idx = max(range(curr_size), key=lambda i: a[i])

        if max_idx != curr_size - 1:
            flip(a, max_idx + 1)
            flip(a, curr_size)

    return a
```

```id="z7k3v1"
func flip[T any](a []T, k int) {
    for i := 0; i < k/2; i++ {
        a[i], a[k-1-i] = a[k-1-i], a[i]
    }
}

func PancakeSort[T constraints.Ordered](a []T) {
    n := len(a)

    for currSize := n; currSize > 1; currSize-- {
        maxIdx := 0
        for i := 1; i < currSize; i++ {
            if a[i] > a[maxIdx] {
                maxIdx = i
            }
        }

        if maxIdx != currSize-1 {
            flip(a, maxIdx+1)
            flip(a, currSize)
        }
    }
}
```