Cycle Sort

Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm. It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result.

Unlike nearly every other sort, items are never written elsewhere in the array simply to push them out of the way of the action. Each value is either written zero times, if it's already in its correct position, or written one time to its correct position. This matches the minimal number of overwrites required for a completed in-place sort.

public IList CycleSort(IList arrayToSort)
{
    int writes = 0;
    for (int cycleStart = 0; cycleStart < arrayToSort.Count; cycleStart++)
    {
        object item = arrayToSort[cycleStart];
        int pos = cycleStart;

        do
        {
            int to = 0;
            for (int i = 0; i < arrayToSort.Count; i++)
            {
                if (i != cycleStart && ((IComparable)arrayToSort[i]).CompareTo(item) < 0)
                {
                    to++;
                }
            }
            if (pos != to)
            {
                while (pos != to && ((IComparable)item).CompareTo(arrayToSort[to]) == 0)
                {
                    to++;
                }

                object temp = arrayToSort[to];
                arrayToSort[to] = item;
                RedrawItem(to);
                item = temp;
                RedrawItem(cycleStart);
                pnlSamples.Refresh();
                if (chkCreateAnimation.Checked)
                    SavePicture();
                writes++;
                pos = to;
            }
        } while (cycleStart != pos);
    }
    return arrayToSort;
}