Cycle sort

Place each value directly into its final sorted index, writing every element to the array at most once.

Time O(n²)Space O(1)Code C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Cycle sort works out the final index for each value directly, the count of values smaller than it, and writes it there once, instead of swapping repeatedly like a bubble or insertion sort. Placing one value can displace whatever was already sitting in its target slot; that displaced value is then carried to its own correct slot, continuing the cycle until it returns to the index where the cycle started. Because every element is written to the array at most once, this is the sort to reach for when writes are far more costly than reads or comparisons.

Code

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

Tips

Minimises the number of writes, not comparisons: it still makes close to n squared comparisons, but writes each element at most once.
Not stable, though it still works correctly when the array has duplicate values.

In the .NET library

Useful when writes are far more costly than reads, for example flash memory wear levelling; ordinary in-memory C# arrays rarely need it, since a write and a read cost about the same there.