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:

Find the maximum element in the unsorted prefix
Flip it to the front
Flip it to its correct final position

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

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

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)
        }
    }
}