---
title: 'Cyclic Sort'
source: 'https://academia.sh/en/courses/advanced-algorithms/cyclic-sort'
course: 'Advanced Algorithms and Problem Solving'
language: en
updated: '2026-08-17T18:07:29+00:00'
license: 'CC BY-SA 4.0'
---

# Cyclic Sort

In-place placement without comparison over a bounded value range; the pattern that never stops on duplicate values, 40 wrong answers on out-of-range values, and what the guard does not fix.

The previous pattern paid the cost of sorting and got a single pass in return. This lesson's
pattern skips sorting entirely. Its idea is one sentence: **if a value tells you its own
destination, no comparison is needed.** When values lie between 1 and n, value `v`'s place is
position `v-1`; every value is sent straight home, and the value that comes out of that home
determines the next placement.

What is paid in exchange is a heavy precondition, and it is in fact **two separate**
preconditions: values must lie **between 1 and n**, and values must be **without
duplicates**. This lesson breaks each separately, because the consequence of breaking each is
also separate: one produces a wrong answer, the other produces **no answer at all**.

## The Pattern's Idea and Its Two Preconditions

The pattern stops at a position and looks at the value there. If the value is not at its
home, it sends the value home; the new value that comes out of that home lands at the same
position and the same operation repeats. If the value is already home, it moves to the next
position. Because every swap puts **at least one value permanently home**, the total swap
count cannot exceed n.

This count's guarantee comes directly from the precondition. When a value is sent home, if
another value already sits there, that value must be **different**; otherwise the swap
advances nothing and the same two values swap places forever.

**PP32.** The array has 12 values and the target range is 1..12; seed `20260218`.
**PP33.** There are three corpora and all three come from the same generator: a **1..n
arrangement** (no duplicates, within range), **duplicate values**, and arrays with two values
moved **out of range**.
**PP34.** The oracle uses one of the comparison-based procedures measured in the Algorithms
course and counts every comparison as one step. The procedure itself is not repeated here.
**PP35.** The pattern is given a **step cap** (400 steps). A run that hits the cap returns
`did not stop` and is counted as diverging from the oracle.

```python
SEED, LENGTH, CORPUS_SIZE = 20260218, 12, 40


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def value_corpus(seed=SEED, n=CORPUS_SIZE, length=LENGTH):
    """Three corpora: 1..n arrangement; duplicate values; out-of-range values."""
    r = generator(seed)
    items = []
    for i in range(n):
        arrangement = list(range(1, length + 1))
        for j in range(length, 1, -1):
            k = r(j)
            arrangement[j - 1], arrangement[k] = arrangement[k], arrangement[j - 1]
        duplicates = [r(length) + 1 for _ in range(length)]
        out_of_range = list(arrangement)
        for _ in range(2):
            out_of_range[r(length)] = length + 2 + r(length)
        items.append({"no": i + 1, "arrangement": arrangement,
                     "duplicates": duplicates, "out_of_range": out_of_range})
    return items


class Counter:
    def __init__(self):
        self.step = 0

    def count(self):
        self.step += 1


def oracle_arrangement(array, s):
    """Comparison-based selection sort. Always correct, always expensive."""
    a = list(array)
    for i in range(len(a)):
        least = i
        for j in range(i + 1, len(a)):
            s.count()
            if a[j] < a[least]:
                least = j
        a[i], a[least] = a[least], a[i]
    return a


def pattern_plain(array, s, cap=400):
    """PRECONDITION: values must be within 1..n and WITHOUT DUPLICATES."""
    a, n = list(array), len(array)
    i = 0
    while i < n:
        s.count()
        if s.step > cap:
            return "did not stop"
        home = a[i] - 1
        if 0 <= home < n and home != i:
            a[i], a[home] = a[home], a[i]
        else:
            i += 1
    return a


def pattern_guarded(array, s, cap=400):
    """Duplicate guard added: no swap if the value at home is already the same."""
    a, n = list(array), len(array)
    i = 0
    while i < n:
        s.count()
        if s.step > cap:
            return "did not stop"
        home = a[i] - 1
        if 0 <= home < n and a[i] != a[home]:
            a[i], a[home] = a[home], a[i]
        else:
            i += 1
    return a


POOL = (("1..n arrangement   ", "arrangement"),
        ("duplicate values   ", "duplicates"),
        ("out-of-range values", "out_of_range"))

K = value_corpus()
print("corpus:", len(K), "arrays x", LENGTH, "values | examples:")
print("  arrangement :", K[0]["arrangement"])
print("  duplicates  :", K[0]["duplicates"])
print("  out_of_range:", K[0]["out_of_range"])
print()
print("pattern    pool                  diverging/40  pattern  oracle   ratio")
for kad, pattern in (("plain    ", pattern_plain), ("guarded  ", pattern_guarded)):
    for ad, key in POOL:
        diverging, pk, ok = 0, 0, 0
        for k in K:
            s1, s2 = Counter(), Counter()
            a = pattern(k[key], s1)
            b = oracle_arrangement(k[key], s2)
            pk, ok = pk + s1.step, ok + s2.step
            diverging += (a != b)
        print(f"{kad}  {ad}  {diverging:8d}  {pk:5d}  {ok:5d}  {ok / pk:5.2f}")
```

```
corpus: 40 arrays x 12 values | examples:
  arrangement : [5, 9, 3, 4, 7, 10, 1, 12, 11, 2, 6, 8]
  duplicates  : [3, 4, 1, 2, 3, 4, 5, 6, 7, 12, 9, 2]
  out_of_range: [5, 9, 3, 4, 7, 18, 1, 12, 11, 2, 6, 16]

pattern    pool                  diverging/40  pattern  oracle   ratio
plain      1..n arrangement            0    826   2640   3.20
plain      duplicate values           40  16040   2640   0.16
plain      out-of-range values        40    801   2640   3.30
guarded    1..n arrangement            0    826   2640   3.20
guarded    duplicate values           39    750   2640   3.52
guarded    out-of-range values        40    801   2640   3.30
```

The first row is the pattern's promise: the same arrangement as the oracle on 40 of 40
inputs, **826** steps against **2640**, a ratio of **3.20**. The result is correct even
though no comparison is ever performed.

The second row carries this topic's most extreme result. On duplicate values, the plain
pattern spends **16,040** steps and the ratio drops to **0.16** — **six times more expensive**
than the oracle. This number is not a slowdown, it is a measure of **not stopping**: all forty
of the forty inputs hit the 400-step cap. Without the cap, the measurement would have finished
on the first input and no result would ever have come out.

The third row shows an entirely different defect. On out-of-range values, the pattern
finishes in **801** steps, ratio **3.30** — even **faster** than the first row — and **wrong
on 40 of 40 inputs**. An out-of-range value has no home; the pattern leaves it where it is and
moves on, and the resulting arrangement differs from the oracle's. There is no warning, no
delay, no sign at all.

## The Guard Fixes Not Stopping, Not the Wrongness

The change that stops the infinite swap is a single comparison: before sending a value home,
check whether the **same value** is already there. If it is, sending it home is pointless and
the position advances instead.

```python
def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def value_corpus(seed, n=40, length=12):
    r = generator(seed)
    items = []
    for i in range(n):
        arrangement = list(range(1, length + 1))
        for j in range(length, 1, -1):
            k = r(j)
            arrangement[j - 1], arrangement[k] = arrangement[k], arrangement[j - 1]
        duplicates = [r(length) + 1 for _ in range(length)]
        out_of_range = list(arrangement)
        for _ in range(2):
            out_of_range[r(length)] = length + 2 + r(length)
        items.append({"arrangement": arrangement, "duplicates": duplicates,
                     "out_of_range": out_of_range})
    return items


def oracle_arrangement(array):
    a = list(array)
    for i in range(len(a)):
        least = i
        for j in range(i + 1, len(a)):
            if a[j] < a[least]:
                least = j
        a[i], a[least] = a[least], a[i]
    return a


def pattern(array, guard, cap=400):
    a, n, i, step = list(array), len(array), 0, 0
    while i < n:
        step += 1
        if step > cap:
            return "did not stop"
        home = a[i] - 1
        if 0 <= home < n and ((a[i] != a[home]) if guard else (home != i)):
            a[i], a[home] = a[home], a[i]
        else:
            i += 1
    return a


example = value_corpus(20260218)[0]
print("duplicate input:", example["duplicates"])
print("  plain pattern  :", pattern(example["duplicates"], False))
print("  guarded pattern:", pattern(example["duplicates"], True))
print("  oracle         :", oracle_arrangement(example["duplicates"]))
print()
print("seed       pattern   pool        diverging/40   ratio")
for seed in (20260218, 20260219):
    K = value_corpus(seed)
    for kad, guard in (("plain   ", False), ("guarded ", True)):
        for key in ("arrangement", "duplicates", "out_of_range"):
            diverging = sum(1 for k in K
                            if pattern(k[key], guard) != oracle_arrangement(k[key]))
            print(f"{seed}  {kad}  {key:12s}  {diverging:8d}   {diverging / 40:.4f}")
```

```
duplicate input: [3, 4, 1, 2, 3, 4, 5, 6, 7, 12, 9, 2]
  plain pattern  : did not stop
  guarded pattern: [1, 2, 3, 4, 5, 6, 7, 4, 9, 2, 3, 12]
  oracle         : [1, 2, 2, 3, 3, 4, 4, 5, 6, 7, 9, 12]

seed       pattern   pool        diverging/40   ratio
20260218  plain     arrangement          0   0.0000
20260218  plain     duplicates          40   1.0000
20260218  plain     out_of_range        40   1.0000
20260218  guarded   arrangement          0   0.0000
20260218  guarded   duplicates          39   0.9750
20260218  guarded   out_of_range        40   1.0000
20260219  plain     arrangement          0   0.0000
20260219  plain     duplicates          40   1.0000
20260219  plain     out_of_range        39   0.9750
20260219  guarded   arrangement          0   0.0000
20260219  guarded   duplicates          40   1.0000
20260219  guarded   out_of_range        39   0.9750
```

The example input shows the mechanism plainly. The plain pattern returns `did not stop`. The
guarded pattern stops and produces `[1, 2, 3, 4, 5, 6, 7, 4, 9, 2, 3, 12]`; the oracle's
answer is `[1, 2, 2, 3, 3, 4, 4, 5, 6, 7, 9, 12]`. They are not the same — **the guard fixed
not stopping, it did not fix the wrongness.** Diverging inputs dropped from 40 to **39**,
which by the resolution rule is not even a **measured** difference, because it stays at the
same order of magnitude.

**PP36.** The second corpus comes from seed `20260219`. In twelve of twelve rows, diverging
inputs are either 0 or 39–40; the result does not depend on the corpus.
**PP37.** A gap between 39 and 40 in 40 inputs **counts as unmeasured**; the swaps between the
two corpora (39/40 on duplicates, 40/39 on out-of-range) are therefore not a trend.

## The Precondition Belongs Not to the Pattern but to the Pattern-Question Pair

So far only one question has been asked: **what will the arrangement itself be.** The same
pattern, with the same broken inputs, can also be used to answer a different question:
**which values from 1..n are missing.** Here the pattern uses the arrangement not as a goal
but as an **intermediate product**; positions that are not home directly give the missing
values.

**PP38.** In this measurement the pattern is the **guarded** form, and the answer is the list
of positions not at home. The oracle searches for each value by scanning the array.
**PP39.** The question changed; the pattern, oracle, corpus, and seed did not.

```python
def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def value_corpus(seed, n=40, length=12):
    r = generator(seed)
    items = []
    for i in range(n):
        arrangement = list(range(1, length + 1))
        for j in range(length, 1, -1):
            k = r(j)
            arrangement[j - 1], arrangement[k] = arrangement[k], arrangement[j - 1]
        duplicates = [r(length) + 1 for _ in range(length)]
        out_of_range = list(arrangement)
        for _ in range(2):
            out_of_range[r(length)] = length + 2 + r(length)
        items.append({"arrangement": arrangement, "duplicates": duplicates,
                     "out_of_range": out_of_range})
    return items


class Counter:
    def __init__(self):
        self.step = 0

    def count(self):
        self.step += 1


def oracle_missing(array, s):
    """Searches for every value in 1..n by scanning the array."""
    missing = []
    for v in range(1, len(array) + 1):
        found = False
        for x in array:
            s.count()
            if x == v:
                found = True
                break
        if not found:
            missing.append(v)
    return missing


def pattern_missing(array, s, cap=400):
    """First places, then collects the positions not at home."""
    a, n = list(array), len(array)
    i = 0
    while i < n:
        s.count()
        if s.step > cap:
            return "did not stop"
        home = a[i] - 1
        if 0 <= home < n and a[i] != a[home]:
            a[i], a[home] = a[home], a[i]
        else:
            i += 1
    missing = []
    for j in range(n):
        s.count()
        if a[j] != j + 1:
            missing.append(j + 1)
    return missing


print("seed       pool        diverging/40  pattern  oracle   ratio")
for seed in (20260218, 20260219):
    K = value_corpus(seed)
    for key in ("arrangement", "duplicates", "out_of_range"):
        diverging, pk, ok = 0, 0, 0
        for k in K:
            s1, s2 = Counter(), Counter()
            a = pattern_missing(k[key], s1)
            b = oracle_missing(k[key], s2)
            pk, ok = pk + s1.step, ok + s2.step
            diverging += (a != b)
        print(f"{seed}  {key:12s}  {diverging:8d}  {pk:5d}  {ok:5d}"
              f"  {ok / pk:5.2f}")
print()
K = value_corpus(20260218)
print("out-of-range example array:", K[0]["out_of_range"])
print("  pattern missing:", pattern_missing(K[0]["out_of_range"], Counter()))
print("  oracle missing :", oracle_missing(K[0]["out_of_range"], Counter()))
```

```
seed       pool        diverging/40  pattern  oracle   ratio
20260218  arrangement          0   1306   3120   2.39
20260218  duplicates           0   1230   3531   2.87
20260218  out_of_range         0   1281   3536   2.76
20260219  arrangement          0   1313   3120   2.38
20260219  duplicates           0   1233   3525   2.86
20260219  out_of_range         0   1294   3548   2.74

out-of-range example array: [5, 9, 3, 4, 7, 18, 1, 12, 11, 2, 6, 16]
  pattern missing: [8, 10]
  oracle missing : [8, 10]
```

Six of six rows give diverging inputs of **zero**. The same pattern, the same duplicate and
out-of-range inputs, two corpora — and no divergence at all. The rows that read 39 and 40 in
the previous table read 0 here.

The only thing that changed is the **question**. "What will the arrangement be" requires
every value in the array to have a home; "which values are missing" does not, because a
homeless value's position does not affect the answer. The pattern's precondition lies not in
the pattern's own code, but in **which question the pattern is answering**.

The rule that follows from this holds for the entire topic: **a pattern's precondition is not
defined when the pattern's name is asked, it is defined once the question asked is fixed.**
The sentence "cyclic sort does not work with duplicate values" is false in this table; the
correct sentence is "cyclic sort does not give the correct answer to the **arrangement
question** with duplicate values."

## Three Numbers

| Metric | Oracle | Pattern | Diverging input |
|---|---|---|---|
| Arrangement, 1..n values | 2640 steps | 826 steps | **0/40** |
| Arrangement, duplicates, plain pattern | 2640 steps | 16,040 steps | **40/40** |
| Arrangement, duplicates, guarded pattern | 2640 steps | 750 steps | **39/40** |
| Arrangement, out-of-range | 2640 steps | 801 steps | **40/40** |
| Missing value, out-of-range | 3536 steps | 1281 steps | **0/40** |

The second row is a measure of not stopping, the third row of silent wrongness, the fifth row
of the question changing. In none of the five rows can the correct rows be picked out by
looking at the step column.

## Summary

- Cyclic sort performs no comparison at all; it sends every value straight to position `v-1`,
  and total swaps never exceed n.
- The pattern has two separate preconditions, and their breakdowns lead to separate
  consequences: duplicate values lead to **not stopping**, out-of-range values lead to
  **silent wrongness**.
- On duplicate input, the plain pattern hits the step cap on 40 of 40 inputs and the ratio
  drops to 0.16; on out-of-range input it finishes in 801 steps and is wrong on 40 of 40.
- The duplicate guard removes not stopping but drops diverging inputs on the arrangement
  question only from 40 to 39.
- When the same pattern answers "which values are missing," diverging inputs are zero on six
  of six measurements; the precondition belongs not to the pattern but to the
  pattern-question pair.

## Next Step

The five patterns so far held the entire input in hand: the array could be seen start to end,
revisited at any position. The next pattern loses that ability. Values **flow one at a time**,
and after each new value a question must be answered: what is the median of what has been
seen so far. The pattern holds two heaps, and its precondition is that these two heaps stay
**balanced**. The next lesson will count how many wrong medians appear at how many steps once
that balance breaks.