Pancake sort

O(n²)

Pancake sort may only reverse a prefix of the array (a "flip", like flipping a stack of pancakes with a spatula). Each round it finds the largest unsorted value, flips it to the front, then flips it down to the end of the unsorted region. It is more a puzzle than a practical sort — O(n²) comparisons and O(n) flips.

Array
Edit the input and press Play

How it works

  1. Find the largest value in the unsorted prefix.
  2. Flip the prefix so that value moves to the front.
  3. Flip the whole unsorted prefix so the value lands at its final position at the end.
  4. Shrink the unsorted region by one and repeat.

Pseudocode

1pancakeSort(a):                     # O(n²)2  for size = n down to 2:3    mi ← index of the max in a[0..size-1]4    if mi ≠ size-1:5      flip(a, mi)                    # bring the max to the front6      flip(a, size-1)                # flip it down to its place7  # flip(a, k) reverses a[0..k]