Skip to content
Tutorials Center
My learning

Topics

Lesson 88 of 225 · Sorting

Cycle, Gnome, Pancake and Bitonic Sort

Meet four unusual sorting algorithms in Python: gnome sort, cycle sort with minimal writes, pancake sorting with prefix flips, and bitonic sort networks.

You already know the workhorses: merge sort, quick sort and heap sort. Yet computer science is full of sorting algorithms designed for strange constraints. Maybe writing to memory is expensive. Maybe the only allowed operation is flipping a prefix of the array. Maybe the comparisons must be fixed in advance so that hardware can run them in parallel.

This lesson covers four of these specialists. You will rarely need them in everyday code, but each one teaches a real idea: gnome sort is the simplest possible sort, cycle sort minimizes writes, pancake sort counts a special kind of move, and bitonic sort is a sorting network that runs on GPUs and in hardware.

Gnome sort: the garden gnome

A garden gnome sorts a row of flower pots like this: look at the pot next to you and the one before it. If they are in order, step forward. If not, swap them and step back. At the start of the row, step forward.

That is the whole algorithm. It is like insertion sort written with one loop and no inner loop.

Python Gnome sort with a step counter

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sorted input takes n steps, reversed input takes about n². Like insertion sort, it is O(n²) in the worst case, O(n) on sorted data, stable, and in-place. Use it to teach, not to ship.

Cycle sort: the fewest possible writes

Writing to memory is cheap in RAM, but not always: flash memory and EEPROM wear out with each write, and some networked stores charge per update. For those cases we want an algorithm that writes each element at most once, directly into its final position. That is cycle sort, and it is optimal in the number of writes.

The idea: for any item, count how many elements are smaller. That count is the index where the item belongs. Put it there, pick up the item that was there, and repeat. Following one chain of displaced items until you return to the start is a cycle.

flowchart LR
    A["Take item x at index start"] --> B["Count smaller items to the right: pos = start + count"]
    B --> C{"pos == start ?"}
    C -- "yes" --> D["Already in place, move on"]
    C -- "no" --> E["Skip duplicates, write x at pos, pick up the old value"]
    E --> F{"Back at start of the cycle?"}
    F -- "no" --> B
    F -- "yes" --> D

One cycle: place the item you hold, pick up the displaced one, and continue until the cycle closes.

Finding each position by counting costs O(n), so total time is O(n²), but writes are at most n − 1 (items already in place cost zero).

Python Cycle sort and write counts

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Cycle sort is not stable and does heavy comparison work, so choose it only when writes, not comparisons, are the scarce resource.

Pancake sorting: only prefix flips allowed

Picture a stack of pancakes of different sizes. Your only tool is a spatula that you slide under the top k pancakes and flip, reversing that prefix. How do you get the biggest on the bottom and the smallest on top?

The strategy is simple, and it is the only sorting algorithm in this lesson where the moves are the whole point:

  1. Find the largest pancake not yet placed.
  2. Flip the stack so it comes to the top (skip this if it is already on top).
  3. Flip again so that it lands at the bottom of the unsorted part.
  4. Shrink the unsorted part by one and repeat.

Each pancake needs at most two flips, so at most 2n − 3 flips sort a stack. The exact minimum number of flips is a famously hard problem; Bill Gates co-authored an early paper bounding it.

Python Pancake sort, showing every flip

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You will see this problem in interviews and puzzle books. It also has a real application: burnt pancake variants model reversals in genome rearrangement.

Bitonic sort: a sorting network

All the algorithms so far decide what to compare next based on earlier results. A sorting network does not. It is a fixed list of compare-and-swap operations, the same for every input of that size. That sounds restrictive, but it has a huge benefit: the comparisons in one stage are independent, so a GPU, an FPGA or a SIMD unit can do them all at the same time.

Bitonic sort is the best-known such network. A sequence is bitonic if it first rises and then falls (or is a rotation of such a sequence). The algorithm builds bigger and bigger bitonic sequences, then merges them with a clean "half-cleaner" step: compare element i with element i + n/2 and swap to put smaller values in the first half. Both halves are then bitonic and every value in the first half is no larger than any in the second.

flowchart TD
    A["Sort 2 halves in opposite directions: ascending then descending"] --> B["Result is a bitonic sequence"]
    B --> C["Half-cleaner: compare i with i + n/2"]
    C --> D["Left half holds the smaller values, right half the larger"]
    D --> E["Recursively merge each half"]
    E --> F["Sorted"]

Bitonic merge: one compare layer splits the data, then each half is merged the same way.

The array length must be a power of two. The comparison pattern for the iterative version uses a neat bit trick: partner of i at distance j is i ^ j, and the direction depends on bit k of i (see bit manipulation).

Python Iterative bitonic sort and its fixed comparator count

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Bitonic sort performs O(n log² n) comparisons, more than merge sort's O(n log n). On a single CPU it loses badly. On hardware with thousands of parallel comparators, its depth of only O(log² n) stages makes it excellent. This is why you meet it in GPU libraries and sorting hardware.

Strand sort: pulling out sorted strands

Strand sort repeatedly pulls an increasing subsequence (a strand) out of the input and merges it into a result list. Take the first item as the start of a strand, scan the rest, and move every item that is not smaller than the strand's last item into the strand. Merge the strand with the output so far, then repeat until the input is empty.

On random data it needs O(n^2) time, because each pass removes only a few items. On data that is already sorted it finishes in one pass, O(n), and on reverse-sorted data each strand has one item, which gives the O(n^2) worst case. The extra lists cost O(n) space. It is mostly a teaching example of merging runs, which is the same idea that powers TimSort.

Python Strand sort

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Choosing among the oddballs

Algorithm Time Special strength Stable
Gnome sort O(n²), O(n) sorted Tiny code, one loop Yes
Cycle sort O(n²) Minimum possible writes No
Pancake sort O(n²) Needs only prefix reversals No
Bitonic sort O(n log² n) Fixed comparisons, parallel No

For ordinary work, use Python's built-in sorted, which is Timsort. For non-comparison alternatives, see counting, radix and bucket sort.

Common mistakes

  • Using bitonic sort on any length. The basic network needs a power of two; pad with large sentinel values if necessary.
  • Forgetting duplicates in cycle sort. Without the while item == a[pos] skip, equal values cause infinite loops.
  • Counting a swap as one write. A swap changes two cells; compare algorithms by cell writes when write cost is the concern.
  • Flipping the wrong prefix in pancake sort. The flip length is the index plus one, not the index.
  • Expecting stability. Cycle, pancake and bitonic sort can reorder equal items.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What is cycle sort optimized for?

    Each element is written directly to its final position, at most once, which suits memory where writes are costly.
  2. 2. In pancake sort, what is the only allowed move?

    A spatula flips the top k pancakes, which reverses the first k elements.
  3. 3. How many flips does the pancake strategy need per pancake at most?

    One flip brings the largest to the top and one flip sends it to the bottom of the unsorted part.
  4. 4. Why is bitonic sort popular on GPUs despite doing O(n log^2 n) comparisons?

    A sorting network never depends on data, so every stage can be executed by many comparators at once.
  5. 5. What input does gnome sort handle fastest?

    On sorted data the gnome never has to swap, so it just walks forward once.

Summary

  • Gnome sort is a one-loop version of insertion sort: O(n²), stable, trivial to write.
  • Cycle sort places each element once, giving the minimum number of writes but O(n²) time and no stability.
  • Pancake sort uses only prefix reversals and needs at most about 2n flips.
  • Bitonic sort is a sorting network: fixed comparisons, O(n log² n) work, O(log² n) parallel depth, power-of-two lengths.
  • In everyday code, prefer the built-in sort; reach for these when the constraint (writes, flips, parallel hardware) demands it.

Next: Trees