Cycle Sort

Cycle sort treats the mapping from current positions to sorted positions as a set of cycles. For the value at cycleStart, it counts smaller values to find the final position, writes the value there, and carries the displaced value to its own final position. The rotation ends when the displaced chain returns to cycleStart.

For distinct values, every displaced element is written directly to its final position and never moved again. That minimizes writes among comparison sorts that reuse the input array, while repeatedly counting smaller suffix values still revisits the remainder for each cycle. Duplicate values require advancing past equal values so a cycle does not keep exchanging indistinguishable entries.

VisualizationVisualizationComplexityComplexity

Visualization

The trace separates comparisons from writes. A scan computes the rank of the carried value, then one overwrite places it and picks up the displaced value. Equal values are skipped when selecting the destination.

Complexity

n

number of elements in the array

TimeSpace

• Best
• Average
• Worst

Boundary and implementation

Cycle sort is unstable: placing a duplicate after equal destinations does not preserve the original order among equal records. The minimum-write argument is strongest for distinct keys, where each displaced element needs one final-position write. It is a niche choice when writes are substantially more expensive than reads; production sorts usually prefer fewer repeated scans.

C# implementation returning the write count

public static int CycleSort(int[] values)
{
    var writes = 0;
    for (var start = 0; start < values.Length - 1; start++)
    {
        var item = values[start];
        var position = start;
        for (var i = start + 1; i < values.Length; i++)
            if (values[i] < item) position++;
 
        if (position == start) continue;
        while (item == values[position]) position++;
        (item, values[position]) = (values[position], item);
        writes++;
 
        while (position != start)
        {
            position = start;
            for (var i = start + 1; i < values.Length; i++)
                if (values[i] < item) position++;
            while (item == values[position]) position++;
            (item, values[position]) = (values[position], item);
            writes++;
        }
    }
    return writes;
}

Questions

Why does Cycle Sort perform few writes but many comparisons?

It computes each final position by scanning and counting smaller values, then writes directly to that position. Avoiding intermediate writes does not avoid the repeated scans.

Why must duplicate destinations be skipped?

Writing a value onto an equal value would not advance the cycle and can repeat indefinitely. Advancing past equal entries selects the next valid slot.

References

• B. K. Haddon, “Cycle-Sort: A Linear Sorting Method” — the original primary paper deriving sorting from the cycle decomposition of a permutation.
• The Computer Journal, Volume 33 bibliography — bibliographic record for Haddon’s 1990 Cycle-Sort paper.