Cycle Sort

Cycle sort is a comparison-based sorting algorithm designed to minimize the number of writes. Each element is moved directly to its correct position by following cycles in the permutation defined by the array.

This makes it useful in situations where write operations are expensive, such as EEPROM or flash memory.

Problem

Given a sequence $A$ of length $n$ , reorder it such that

A[0] \le A[1] \le \cdots \le A[n-1]

Key Idea

Each element belongs to a specific position in the sorted order. For an element $A[i]$ , count how many elements are smaller than it. That count determines its final index.

If the element is not already in the correct position, place it there, then continue the cycle with the displaced element.

Algorithm

cycle_sort(A):
    n = length(A)

    for start from 0 to n - 2:
        item = A[start]

        pos = start
        for i from start + 1 to n - 1:
            if A[i] < item:
                pos = pos + 1

        if pos == start:
            continue

        while item == A[pos]:
            pos = pos + 1

        swap(item, A[pos])

        while pos != start:
            pos = start
            for i from start + 1 to n - 1:
                if A[i] < item:
                    pos = pos + 1

            while item == A[pos]:
                pos = pos + 1

            swap(item, A[pos])

Example

Let

A = [3, 1, 2, 0]

Step 1:

Element 3 belongs at index 3

→ [0, 1, 2, 3]

The cycle completes in a single pass.

Correctness

Each cycle places elements into their correct final positions. Since every element is eventually placed according to the number of smaller elements, the final arrangement is sorted.

Each cycle resolves a permutation cycle, and no element is moved more times than necessary.

Complexity

case	comparisons	time
best	$O(n^2)$	$O(n^2)$
worst	$O(n^2)$	$O(n^2)$
average	$O(n^2)$	$O(n^2)$

Space complexity:

O(1)

Write Complexity

Cycle sort minimizes writes:

Each element is written at most once
Total writes are at most $n$

This is optimal among comparison-based sorts.

Properties

in-place
not stable
minimizes number of writes
based on permutation cycles

When to Use

Cycle sort is useful when write operations are expensive or limited. It is rarely used for general-purpose sorting due to its quadratic time complexity, but it is valuable in specialized systems.

Implementation

def cycle_sort(a):
    n = len(a)

    for start in range(n - 1):
        item = a[start]

        pos = start
        for i in range(start + 1, n):
            if a[i] < item:
                pos += 1

        if pos == start:
            continue

        while item == a[pos]:
            pos += 1

        a[pos], item = item, a[pos]

        while pos != start:
            pos = start
            for i in range(start + 1, n):
                if a[i] < item:
                    pos += 1

            while item == a[pos]:
                pos += 1

            a[pos], item = item, a[pos]

    return a

func CycleSort[T constraints.Ordered](a []T) {
    n := len(a)

    for start := 0; start < n-1; start++ {
        item := a[start]

        pos := start
        for i := start + 1; i < n; i++ {
            if a[i] < item {
                pos++
            }
        }

        if pos == start {
            continue
        }

        for item == a[pos] {
            pos++
        }

        a[pos], item = item, a[pos]

        for pos != start {
            pos = start
            for i := start + 1; i < n; i++ {
                if a[i] < item {
                    pos++
                }
            }

            for item == a[pos] {
                pos++
            }

            a[pos], item = item, a[pos]
        }
    }
}