user
|  |
| --- |
| This page uses content from **Wikipedia**. The original article was at Cycle\_sort. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |

From the the Wikipedia entry on cycle sorting:

:   **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.

:   Minimizing the number of writes is useful when making writes to some huge data set is very expensive, such as with EEPROMs like Flash memory where each write reduces the lifespan of the memory.

See also

* Youtube Visualization and audibilization of Cycle Sort algorithm.
assistant
(formerly Perl 6)

```
sub cycle_sort ( @nums ) {
    my $writes = 0;

    # Loop through the array to find cycles to rotate.
    for @nums.kv -> $cycle_start, $item is copy {

        # Find where to put the item.
        my $pos = $cycle_start
                + @nums[ $cycle_start ^.. * ].grep: * < $item;

        # If the item is already there, this is not a cycle.
        next if $pos == $cycle_start;

        # Otherwise, put the item there or right after any duplicates.
        $pos++ while $item == @nums[$pos];
        ( @nums[$pos], $item ) .= reverse;
        $writes++;

        # Rotate the rest of the cycle.
        while $pos != $cycle_start {

            # Find where to put the item.
            $pos = $cycle_start
                 + @nums[ $cycle_start ^.. * ].grep: * < $item;

            # Put the item there or right after any duplicates.
            $pos++ while $item == @nums[$pos];
            ( @nums[$pos], $item ) .= reverse;
            $writes++;
        }
    }

    return $writes;
}

my @a = <0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6>;

say @a;
say 'writes ', cycle_sort(@a);
say @a;

```

Output:

```
0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6
writes 10
0 0 1 1 2 2 2 2 3.5 4 5 6 7 8 9

```