Pancake Sort
- Ω( n2 )
- Θ( n2 )
- O( n2 )
- space O( 1 )
Array
Comparator strip
Index down, time to the right
- Comparisons count only element-against-element checks; loop and index checks are never counted.
- Reads and writes include reads and writes to helper buffers (merge, counting, radix, bucket and tim sort).
- A swap counts once, as a swap. It is never also counted as a read or a write.
- Real time is the average time of the counted sort on this device over repeated runs, measured once before playback and independent of animation speed. Visual time is the time spent animating, excluding pauses.
How pancake sort works
Pancake sort sorts with a single operation: flip a prefix of the array, like sliding a spatula under a stack of pancakes and turning the top part over. For each shrinking prefix it finds the largest element, flips it to the front, then flips the whole prefix to send it to the end.
Read more
Each flip is drawn as a series of swaps between mirrored positions. It needs at most 2n flips but each flip costs O(n), so the total is O(n²).
| Best time | Ω( n2 ) | poor |
|---|---|---|
| Average time | Θ( n2 ) | poor |
| Worst time | O( n2 ) | poor |
| Worst space | O( 1 ) | good |
Big O notation gives the lower, average and upper bounds of an algorithm. Time complexity bounds the number of operations; space complexity bounds the extra memory it uses.