Pancake Sort
The only move allowed is flipping a prefix. Repeatedly flip the largest unsorted value to the top, then flip it down into place.
- Category
- Sorting
- Time complexity
- O(n²)
- Space complexity
- O(1)
Pseudocode
for size = n down to 2 find max in a[0..size) flip it to the front flip front..size to its slot
Reference implementation
for size in range(n, 1, -1):
mi = index of max in a[:size]
flip(a, mi) # max to top
flip(a, size-1) # top to place