Summary

Pancake sorting is a mathematical problem and sorting algorithm where the only allowed operation is to reverse the elements of some prefix of the sequence. Imagine a stack of pancakes of different sizes; your goal is to organize them from smallest (top) to largest (bottom) using a spatula. You can insert the spatula at any point and "flip" all pancakes above it. Unlike traditional algorithms that minimize comparisons, the goal here is often to minimize the number of flips.

How it Works

• Start with the current size of the unsorted array equal to $n$.

• Find the index of the maximum element (mi) within the current unsorted portion arr[0...curr_size-1].

• If the maximum element is not already at the end of the unsorted portion:

• 1. Flip to Top: Perform a flip at index mi. This reverses the sub-array from 0 to mi, moving the maximum element to index 0.

• 2. Flip to Position: Perform a flip at index curr_size - 1. This reverses the sub-array from 0 to curr_size - 1, moving the maximum element from index 0 to its correct sorted position at the end.

• Reduce the current size by one and repeat the process until the array is sorted.