user
Sort an array of integers (of any convenient size) into ascending order using Circlesort.

In short, compare the first element to the last element, then the second element to the second last element, etc.

Then split the array in two and recurse until there is only one single element in the array, like this:

```
Before:
6 7 8 9 2 5 3 4 1
After:
1 4 3 5 2 9 8 7 6

```

Repeat this procedure until quiescence (i.e. until there are no swaps).

Show both the initial, unsorted list and the final sorted list. (Intermediate steps during sorting are optional.)

Optimizations (like doing *0.5 log2(n)* iterations and then continue with an Insertion sort) are optional.

Pseudo code:

```
 function circlesort (index lo, index hi, swaps)
 {
   if lo == hi return (swaps)
   high := hi
   low := lo
   mid := int((hi-lo)/2)
   while lo < hi {
     if  (value at lo) > (value at hi) {
        swap.values (lo,hi)
        swaps++
     }
     lo++
     hi--
   }
   if lo == hi
     if (value at lo) > (value at hi+1) {
         swap.values (lo,hi+1)
         swaps++
     }
   swaps := circlesort(low,low+mid,swaps)
   swaps := circlesort(low+mid+1,high,swaps)
   return(swaps)
 }
 while circlesort (0, sizeof(array)-1, 0)

```

See also

* For more information on Circle sorting, see Sourceforge.
assistant
(formerly Perl 6)

The given algorithm can be simplified in several ways. There's no need to compute the midpoint, since the hi/lo will end up there. The extra swap conditional can be eliminated by incrementing hi at the correct moment inside the loop. There's no need to
pass accumulated swaps down the call stack.

This does generic comparisons, so it works on any ordered type, including numbers or strings.

```
sub circlesort (@x, $beg, $end) {
    my $swaps = 0;
    if $beg < $end {
        my ($lo, $hi) = $beg, $end;
        repeat {
            if @x[$lo] after @x[$hi] {
                @x[$lo,$hi] .= reverse;
                ++$swaps;
            }
            ++$hi if --$hi == ++$lo
        } while $lo < $hi;
        $swaps += circlesort(@x, $beg, $hi);
        $swaps += circlesort(@x, $lo, $end);
    }
    $swaps;
}

say my @x = (-100..100).roll(20);
say @x while circlesort(@x, 0, @x.end);

say @x = <The quick brown fox jumps over the lazy dog.>;
say @x while circlesort(@x, 0, @x.end);

```

Output:

```
16 35 -64 -29 46 36 -1 -99 20 100 59 26 76 -78 39 85 -7 -81 25 88
-99 -78 16 20 36 -81 -29 46 25 59 -64 -7 39 26 88 -1 35 85 76 100
-99 -78 -29 -81 16 -64 -7 20 -1 39 25 26 36 46 59 35 76 88 85 100
-99 -81 -78 -64 -29 -7 -1 16 20 25 26 35 36 39 46 59 76 85 88 100
The quick brown fox jumps over the lazy dog.
The brown fox jumps lazy dog. quick over the
The brown dog. fox jumps lazy over quick the
```