Pancake Sort

Pancake sort works under an unusual constraint: the only legal move reverses a prefix beginning at index 0. To place the largest value in the unsorted region, one flip brings it to the front and another moves it to the region’s right boundary. Then the boundary shrinks.

The settled suffix is the invariant. After boundary end has been processed, every position to its right holds its final value and later flips cannot reach it. The price of the restricted move is repeated scanning: every new boundary requires another search for the maximum of the live prefix.

VisualizationVisualizationComplexityComplexity

Visualization

Each move reverses [0..k]. When the live maximum is not already at the boundary, one flip brings it to the front and a second carries it to the boundary. At most two prefix reversals settle each position.

Complexity

TimeSpace

• Worst/Average/Best: Θ(n²)

n

number of elements in the array

Prefix reversals, stability, and scan cost

The direct algorithm mutates the array in place. It is unstable because reversing a prefix can carry equal keys past each other. Every shrinking prefix is still scanned for its maximum, even when that maximum already sits at the boundary. A preliminary sortedness check helps only with the fully sorted case. It does not change the quadratic scan pattern.

C# implementation

public static void PancakeSort(int[] values)
{
    for (var end = values.Length - 1; end > 0; end--)
    {
        var max = 0;
        for (var i = 1; i <= end; i++)
            if (values[i] > values[max]) max = i;
 
        if (max == end) continue;
        if (max > 0) Flip(values, max);
        Flip(values, end);
    }
}
 
private static void Flip(int[] values, int end)
{
    for (var left = 0; left < end; left++, end--)
        (values[left], values[end]) = (values[end], values[left]);
}

Every mutation belongs to a prefix reversal. The implementation never uses an arbitrary swap.

References

• Gates and Papadimitriou, “Bounds for Sorting by Prefix Reversal”