Cycle Sort

Cycle sort is the sorting algorithm that writes to memory the fewest possible times. Instead of comparing neighbors, it figures out exactly where each value belongs and puts it there in one move — then picks up whatever it displaced and repeats. Every value is written at most once, which makes it the go-to when writes are expensive (think flash memory) or when you must count writes.

The array is a permutation of slots, and those slots form cycles: 3 wants slot 2, whoever is in slot 2 wants some other slot, and so on, until the chain loops back to the slot we started from. Cycle sort resolves one whole cycle before moving on.

Intuition

Picture a musical-chairs scramble where every person already knows their assigned chair. You walk up to chair 0, lift out whoever is sitting there, and carry them to their correct chair. But that chair is occupied — so you set your person down, lift out the new occupant, and carry them to their chair. You keep doing this hand-off until the person you are carrying belongs back in chair 0, the seat you first emptied. That closes the cycle: everyone you touched is now seated correctly, and you never set anyone down twice.

The clever part is how you find each person's chair without a sorted reference: just count how many people are shorter (smaller-valued). If k items are smaller than the value in your hands, it belongs at index k. No comparisons between neighbors, no repeated passes — each value goes straight home.

Walk through it

Step through the animation on the right. The cycle_start pointer (below) marks the slot we emptied to begin the cycle; the pos pointer (above) shows where the held value is headed; the floating held = ... label is the value currently in our hands.

We begin at index 0, holding 3. Counting the items smaller than 3 (those are 1 and 2) gives 2, so 3 belongs at index 2. We drop 3 there and pick up the 5 it displaced. Now holding 5: four items are smaller, so it goes to index 4, displacing 2. Holding 2: one item (1) is smaller, so it goes to index 1, displacing 1. Holding 1: nothing is smaller, so its home is index 0 — the very slot we emptied. Writing 1 there closes the cycle, and [1, 2, 3, 4, 5] is sorted. The remaining cycle starts (1, 2, 3) each find their value already in place and are skipped.

The code, line by line

def cycle_sort(a):
    n = len(a)
    for cycle_start in range(n - 1):
        item = a[cycle_start]
        pos = cycle_start
        for k in range(cycle_start + 1, n):
            if a[k] < item:
                pos += 1
        if pos == cycle_start:
            continue
        while item == a[pos]:
            pos += 1
        a[pos], item = item, a[pos]
        while pos != cycle_start:
            pos = cycle_start
            for k in range(cycle_start + 1, n):
                if a[k] < item:
                    pos += 1
            while item == a[pos]:
                pos += 1
            a[pos], item = item, a[pos]
    return a

• Line 3 starts a new cycle at each index (the last element falls into place for free, so the loop stops at n - 1).
• Line 4 picks up the value at cycle_start — this is the first item we carry.
• Lines 5–8 are the heart of it: count how many items are smaller than item. That count, added to cycle_start, is item's sorted index pos.
• Lines 9–10: if pos did not move, item is already home — skip to the next cycle start.
• Lines 11–12 handle duplicates: if the target slot already holds a value equal to item, slide past it so equal values do not endlessly swap with each other.
• Line 13 does the first placement: item goes to pos, and we pick up whatever was there.
• Lines 14–21 are the inner cycle: re-count to find the new held value's home, skip duplicates, and place it — over and over until pos returns to cycle_start, which means the held value belongs in the slot we first emptied and the cycle is closed.

Complexity

Cycle sort trades time for writes. The counting scan inside every placement makes it O(n^2) comparisons — no better than selection sort on that axis. But the number of memory writes is the theoretical minimum: at most n writes total, because each value moves directly to its final slot exactly once. That is why it shows up wherever writes dominate the cost.

When to use / pitfalls

Practice