Jump to content

Sorting Algorithms/Circle Sort

From Rosetta Code
(Redirected from Circle sort)
Task
Sorting Algorithms/Circle Sort
You are encouraged to solve this task according to the task description, using any language you may know.

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.



11l

Translation of: Python
F circle_sort_backend(&A, Int l, r)
   V n = r - l
   I n < 2
      R 0
   V swaps = 0
   V m = n I/ 2
   L(i) 0 .< m
      I A[r - (i + 1)] < A[l + i]
         swap(&A[r - (i + 1)], &A[l + i])
         swaps++
   I (n [&] 1) != 0 & (A[l + m] < A[l + m - 1])
      swap(&A[l + m - 1], &A[l + m])
      swaps++
   R swaps + circle_sort_backend(&A, l, l + m) + circle_sort_backend(&A, l + m, r)

F circle_sort(&l)
   V swaps = 0
   V s = 1
   L s != 0
      s = circle_sort_backend(&l, 0, l.len)
      swaps += s
   R swaps

L(i) 309
   V l = Array(0 .< i)
   V m = copy(l)
   random:shuffle(&l)
   V n = copy(l)
   circle_sort(&l)
   I l != m
      print(l.len)
      print(n)
      print(l)

AArch64 Assembly

Works with: as version Raspberry Pi 3B version Buster 64 bits
/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program circleSort64.s  */
 
/*******************************************/
/* Constantes file                         */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"

/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessSortOk:       .asciz "Table sorted.\n"
szMessSortNok:      .asciz "Table not sorted !!!!!.\n"
szMessSortBefore:   .asciz "Display table before sort.\n"
sMessResult:        .asciz "Value  : @ \n"
szCarriageReturn:   .asciz "\n"
 
.align 4
#TableNumber:      .quad   1,3,6,2,5,9,10,8,4,7
#TableNumber:       .quad   1,2,3,4,5,6,7,8,9,10
#TableNumber:       .quad   9,5,12,8,2,12,6
TableNumber:       .quad   10,9,8,7,6,5,4,3,2,1
                   .equ NBELEMENTS, (. - TableNumber) / 8
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:            .skip 24
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                               // entry of program 
    ldr x0,qAdrszMessSortBefore
    bl affichageMess
    ldr x0,qAdrTableNumber          // address number table
    bl displayTable
1:
    ldr x0,qAdrTableNumber          // address number table
    mov x1,#0
    mov x2,#NBELEMENTS -1           // number of élements 
    mov x3,#0
    bl circleSort
    cmp x0,#0
    bne 1b
    ldr x0,qAdrTableNumber          // address number table
    mov x1,#NBELEMENTS              // number of élements 
    bl displayTable
 
    ldr x0,qAdrTableNumber          // address number table
    mov x1,#NBELEMENTS              // number of élements 
    bl isSorted                     // control sort
    cmp x0,#1                       // sorted ?
    beq 2f                                    
    ldr x0,qAdrszMessSortNok        // no !! error sort
    bl affichageMess
    b 100f
2:                                  // yes
    ldr x0,qAdrszMessSortOk
    bl affichageMess
100:                                // standard end of the program 
    mov x0, #0                      // return code
    mov x8, #EXIT                   // request to exit program
    svc #0                          // perform the system call
 
qAdrszCarriageReturn:     .quad szCarriageReturn
qAdrsMessResult:          .quad sMessResult
qAdrTableNumber:          .quad TableNumber
qAdrszMessSortOk:         .quad szMessSortOk
qAdrszMessSortNok:        .quad szMessSortNok
qAdrszMessSortBefore:     .quad szMessSortBefore
/******************************************************************/
/*     control sorted table                                   */ 
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the number of elements  > 0  */
/* x0 return 0  if not sorted   1  if sorted */
isSorted:
    stp x2,lr,[sp,-16]!          // save  registers
    stp x3,x4,[sp,-16]!          // save  registers
    mov x2,#0
    ldr x4,[x0,x2,lsl #3]
1:
    add x2,x2,#1
    cmp x2,x1
    bge 99f
    ldr x3,[x0,x2, lsl #3]
    cmp x3,x4
    blt 98f                      // smaller -> error
    mov x4,x3                    // A[i-1] = A[i]
    b 1b                         // else loop
98:
    mov x0,#0                    // error
    b 100f
99:
    mov x0,#1                    // ok -> return
100:
    ldp x2,x3,[sp],16            // restaur  2 registers
    ldp x1,lr,[sp],16            // restaur  2 registers
    ret                          // return to address lr x30
/******************************************************************/
/*         circle sort                                              */ 
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the first index */
/* x2 contains the last index */
/* x3 contains number of swaps */
circleSort:
    stp x1,lr,[sp,-16]!          // save  registers
    stp x2,x3,[sp,-16]!          // save  registers
    stp x4,x5,[sp,-16]!          // save  registers
    stp x6,x7,[sp,-16]!          // save  registers
    stp x8,x9,[sp,-16]!          // save  registers
    stp x10,x11,[sp,-16]!        // save  registers
    cmp x1,x2
    beq 99f
    mov x7,x0                    // save address
    mov x8,x1                    // low
    mov x9,x2                    // high
    sub x4,x2,x1
    lsr x4,x4,#1
    mov x10,x4                   // mid
1:                               // start loop
    cmp x1,x2
    bge 3f
    ldr x5,[x0,x1,lsl #3]
    ldr x6,[x0,x2,lsl #3]
    cmp x5,x6
    ble 2f
    str x6,[x0,x1,lsl #3]        // swap values
    str x5,[x0,x2,lsl #3] 
    add x3,x3,#1
2:
    add x1,x1,#1                 // increment lo
    sub x2,x2,#1                 // decrement hi
    b 1b                         // and loop
3:
    cmp x1,x2                    // compare lo hi
    bne 4f                       // not egal
    ldr x5,[x0,x1,lsl #3]
    add x2,x2,#1
    ldr x6,[x0,x2,lsl #3]
    cmp x5,x6 
    ble 4f
    str x6,[x0,x1,lsl #3]        //  swap
    str x5,[x0,x2,lsl #3] 
    add x3,x3,#1
4:
    mov x1,x8                    // low
    mov x2,x10                   // mid
    add x2,x2,x1
    bl circleSort
    mov x3,x0                    // swaps
    mov x0,x7                    // table address
    mov x1,x8                    // low
    mov x2,x10                   // mid
    add x1,x2,x1
    add x1,x1,#1
    mov x2,x9                    // high
    bl circleSort
    mov x3,x0                    // swaps
99:
    mov x0,x3                    // return number swaps
100:
    ldp x10,x11,[sp],16          // restaur  2 registers
    ldp x8,x9,[sp],16            // restaur  2 registers
    ldp x6,x7,[sp],16            // restaur  2 registers
    ldp x4,x5,[sp],16            // restaur  2 registers
    ldp x2,x3,[sp],16            // restaur  2 registers
    ldp x1,lr,[sp],16            // restaur  2 registers
    ret                          // return to address lr x30
/******************************************************************/
/*      Display table elements                                */ 
/******************************************************************/
/* x0 contains the address of table */
displayTable:
    stp x1,lr,[sp,-16]!          // save  registers
    stp x2,x3,[sp,-16]!          // save  registers
    mov x2,x0                    // table address
    mov x3,#0
1:                               // loop display table
    ldr x0,[x2,x3,lsl #3]
    ldr x1,qAdrsZoneConv
    bl conversion10              // décimal conversion 
    ldr x0,qAdrsMessResult
    ldr x1,qAdrsZoneConv         // insert conversion
    bl strInsertAtCharInc
    bl affichageMess             // display message
    add x3,x3,#1
    cmp x3,#NBELEMENTS - 1
    ble 1b
    ldr x0,qAdrszCarriageReturn
    bl affichageMess
100:
    ldp x2,x3,[sp],16            // restaur  2 registers
    ldp x1,lr,[sp],16            // restaur  2 registers
    ret                          // return to address lr x30
qAdrsZoneConv:           .quad sZoneConv
/********************************************************/
/*        File Include fonctions                        */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
Display table before sort.
Value  : 10
Value  : 9
Value  : 8
Value  : 7
Value  : 6
Value  : 5
Value  : 4
Value  : 3
Value  : 2
Value  : 1

Value  : 1
Value  : 2
Value  : 3
Value  : 4
Value  : 5
Value  : 6
Value  : 7
Value  : 8
Value  : 9
Value  : 10

Table sorted.

Action!

Action! language does not support recursion. Therefore an iterative approach with a stack has been proposed.

DEFINE MAX_COUNT="100"
INT ARRAY stack(MAX_COUNT)
INT stackSize

PROC PrintArray(INT ARRAY a INT size)
  INT i

  Put('[)
  FOR i=0 TO size-1
  DO
    IF i>0 THEN Put(' ) FI
    PrintI(a(i))
  OD
  Put(']) PutE()
RETURN

PROC InitStack()
  stackSize=0
RETURN

BYTE FUNC IsEmpty()
  IF stackSize=0 THEN
    RETURN (1)
  FI
RETURN (0)

PROC Push(INT low,high)
  stack(stackSize)=low  stackSize==+1
  stack(stackSize)=high stackSize==+1
RETURN

PROC Pop(INT POINTER low,high)
  stackSize==-1 high^=stack(stackSize)
  stackSize==-1 low^=stack(stackSize)
RETURN

INT FUNC Partition(INT ARRAY a INT low,high)
  INT part,v,i,tmp

  v=a(high)
  part=low-1

  FOR i=low TO high-1
  DO
    IF a(i)<=v THEN
      part==+1
      tmp=a(part) a(part)=a(i) a(i)=tmp
    FI
  OD

  part==+1
  tmp=a(part) a(part)=a(high) a(high)=tmp
RETURN (part)

PROC CircleSort(INT ARRAY a INT size)
  INT swaps,low,high,lo,hi,tmp,mid

  InitStack()
  DO
    swaps=0
    Push(0,size-1)
    WHILE IsEmpty()=0
    DO
      Pop(@low,@high)
      IF low<high THEN
        lo=low hi=high
        WHILE lo<hi
        DO
          IF a(hi)<a(lo) THEN
            tmp=a(lo) a(lo)=a(hi) a(hi)=tmp
            swaps==+1
          FI
          lo==+1 hi==-1
        OD
        IF lo=hi AND a(lo+1)<a(lo) THEN
          tmp=a(lo) a(lo)=a(lo+1) a(lo+1)=tmp
          swaps==+1
        FI
        mid=(lo+hi)/2
        Push(low,mid)
        Push(mid+1,high)
      FI
    OD
  UNTIL swaps=0
  OD
RETURN

PROC Test(INT ARRAY a INT size)
  PrintE("Array before sort:")
  PrintArray(a,size)
  CircleSort(a,size)
  PrintE("Array after sort:")
  PrintArray(a,size)
  PutE()
RETURN

PROC Main()
  INT ARRAY
    a(10)=[1 4 65535 0 3 7 4 8 20 65530],
    b(21)=[10 9 8 7 6 5 4 3 2 1 0
      65535 65534 65533 65532 65531
      65530 65529 65528 65527 65526],
    c(8)=[101 102 103 104 105 106 107 108],
    d(12)=[1 65535 1 65535 1 65535 1
      65535 1 65535 1 65535]
  
  Test(a,10)
  Test(b,21)
  Test(c,8)
  Test(d,12)
RETURN
Output:

Screenshot from Atari 8-bit computer

Array before sort:
[1 4 -1 0 3 7 4 8 20 -6]
Array after sort:
[-6 -1 0 1 3 4 4 7 8 20]

Array before sort:
[10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10]
Array after sort:
[-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10]

Array before sort:
[101 102 103 104 105 106 107 108]
Array after sort:
[101 102 103 104 105 106 107 108]

Array before sort:
[1 -1 1 -1 1 -1 1 -1 1 -1 1 -1]
Array after sort:
[-1 -1 -1 -1 -1 -1 1 1 1 1 1 1]

ALGOL 68

BEGIN # circlesort                                                           #

    # swaps a and b                                                          #
    PRIO =:= = 9;
    OP   =:= = ( REF INT a, b )VOID: BEGIN INT t = a; a := b; b := t END;

    # sorts data in-place and returns a reference to data                    #
    OP   CIRCLESORT = ( REF[]INT data to sort )REF[]INT:
         BEGIN
            PROC circlesort = ( REF[]INT data, INT low, high, swaps so far )INT:
                 IF low >= high THEN swaps so far
                 ELSE
                    INT swaps := swaps so far;
                    INT hi    := high;
                    INT lo    := low;
                    INT mid    = ( hi - lo ) OVER 2;
                    WHILE lo < hi DO
                        IF  data[ lo ] > data[ hi ] THEN
                            data[ lo ] =:= data[ hi ];
                            swaps      +:= 1
                        FI;
                        lo +:= 1;
                        hi -:= 1
                    OD;
                    IF lo = hi AND hi < UPB data THEN
                        IF data[ lo ] > data[ hi + 1 ] THEN
                            data[ lo ] =:= data[ hi + 1 ];
                            swaps      +:= 1
                        FI
                    FI;
                    swaps := circlesort( data, low, low + mid,      swaps );
                    swaps := circlesort( data, low + mid + 1, high, swaps )
                 FI # circlesort # ;

            WHILE circlesort( data to sort, LWB data to sort, UPB data to sort, 0 ) > 0 DO SKIP OD;
            data to sort
         END # CIRCLESORT # ;

    # prints the elements of an array of integers separated by spaces         #
    OP   SHOW = ( []INT list )VOID:
         FOR i FROM LWB list TO UPB list DO
            print( ( " ", whole( list[ i ], 0 ) ) )
         OD # SHOW # ;

    # tests the CIRCLESORT operator                                          #
    PROC test circle sort = ( []INT unsorted )VOID:
         BEGIN
             [ LWB unsorted : UPB unsorted ]INT data := unsorted;
             print( ( "[" ) );
             SHOW unsorted;
             print( ( " ]", newline, "    -> [" ) );
             SHOW CIRCLESORT data;
             print( ( " ]", newline ) )
         END # test circle sort # ;

    # task test case                                                         #
    test circle sort( ( 6, 7, 8, 9, 2, 5, 3, 4, 1 ) );
    # test cases from the Action! sample                                     #
    test circle sort( ( 1, 4, -1, 0, 3, 7, 4, 8, 20, -6 ) );
    test circle sort( ( 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10 ) );
    test circle sort( ( 101, 102, 103, 104, 105, 106, 107, 108 ) );
    test circle sort( ( 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1 ) );
    # additional tests                                                       #
    test circle sort( ( ) );
    test circle sort( ( 1 ) )

END
Output:
[ 6 7 8 9 2 5 3 4 1 ]
    -> [ 1 2 3 4 5 6 7 8 9 ]
[ 1 4 -1 0 3 7 4 8 20 -6 ]
    -> [ -6 -1 0 1 3 4 4 7 8 20 ]
[ 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 ]
    -> [ -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 ]
[ 101 102 103 104 105 106 107 108 ]
    -> [ 101 102 103 104 105 106 107 108 ]
[ 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ]
    -> [ -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 ]
[ ]
    -> [ ]
[ 1 ]
    -> [ 1 ]

ARM Assembly

Works with: as version Raspberry Pi
/* ARM assembly Raspberry PI  */
/*  program circleSort.s  */
 
 /* REMARK 1 : this program use routines in a include file 
   see task Include a file language arm assembly 
   for the routine affichageMess conversion10 
   see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes                       */
/************************************/
.include "../constantes.inc"

/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessSortOk:       .asciz "Table sorted.\n"
szMessSortNok:      .asciz "Table not sorted !!!!!.\n"
szMessSortBefore:   .asciz "Display table before sort.\n"
sMessResult:        .asciz "Value  : @ \n"
szCarriageReturn:   .asciz "\n"
 
.align 4
#TableNumber:      .int   1,3,6,2,5,9,10,8,4,7
#TableNumber:       .int   1,2,3,4,5,6,7,8,9,10
TableNumber:       .int   9,5,12,8,2,12,6
#TableNumber:       .int   10,9,8,7,6,5,4,3,2,1
                   .equ NBELEMENTS, (. - TableNumber) / 4
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:            .skip 24
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                               @ entry of program 
    ldr r0,iAdrszMessSortBefore
    bl affichageMess
    ldr r0,iAdrTableNumber          @ address number table
    bl displayTable
1:
    ldr r0,iAdrTableNumber          @ address number table
    mov r1,#0
    mov r2,#NBELEMENTS -1           @ number of élements 
    mov r3,#0
    bl circleSort
    cmp r0,#0
    bne 1b
    ldr r0,iAdrTableNumber          @ address number table
    mov r1,#NBELEMENTS              @ number of élements 
    bl displayTable
 
    ldr r0,iAdrTableNumber          @ address number table
    mov r1,#NBELEMENTS              @ number of élements 
    bl isSorted                     @ control sort
    cmp r0,#1                       @ sorted ?
    beq 2f                                    
    ldr r0,iAdrszMessSortNok        @ no !! error sort
    bl affichageMess
    b 100f
2:                                  @ yes
    ldr r0,iAdrszMessSortOk
    bl affichageMess
100:                                @ standard end of the program 
    mov r0, #0                      @ return code
    mov r7, #EXIT                   @ request to exit program
    svc #0                          @ perform the system call
 
iAdrszCarriageReturn:     .int szCarriageReturn
iAdrsMessResult:          .int sMessResult
iAdrTableNumber:          .int TableNumber
iAdrszMessSortOk:         .int szMessSortOk
iAdrszMessSortNok:        .int szMessSortNok
iAdrszMessSortBefore:     .int szMessSortBefore
/******************************************************************/
/*     control sorted table                                   */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the number of elements  > 0  */
/* r0 return 0  if not sorted   1  if sorted */
isSorted:
    push {r2-r4,lr}                                    @ save registers
    mov r2,#0
    ldr r4,[r0,r2,lsl #2]
1:
    add r2,#1
    cmp r2,r1
    movge r0,#1
    bge 100f
    ldr r3,[r0,r2, lsl #2]
    cmp r3,r4
    movlt r0,#0
    blt 100f
    mov r4,r3
    b 1b
100:
    pop {r2-r4,lr}
    bx lr                                              @ return 
/******************************************************************/
/*         circle sort                                              */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the first index */
/* r2 contains the last index */
/* r3 contains number of swaps */
circleSort:
    push {r1-r10,lr}           @ save registers
    cmp r1,r2
    beq 99f
    mov r7,r0                  @ save address
    mov r8,r1                  @ low
    mov r9,r2                  @ high
    sub r4,r2,r1
    lsr r4,#1
    mov r10,r4                 @ mid
1:                             @ start loop
    cmp r1,r2
    bge 3f
    ldr r5,[r0,r1,lsl #2]
    ldr r6,[r0,r2,lsl #2]
    cmp r5,r6
    ble 2f
    str r6,[r0,r1,lsl #2]      @ swap values
    str r5,[r0,r2,lsl #2] 
    add r3,r3,#1
2:
    add r1,r1,#1               @ increment lo
    sub r2,r2,#1               @ decrement hi
    b 1b                       @ and loop
3:
    cmp r1,r2                  @ compare lo hi
    bne 4f                     @ not egal
    ldr r5,[r0,r1,lsl #2]
    add r2,r2,#1
    ldr r6,[r0,r2,lsl #2]
    cmp r5,r6 
    ble 4f
    str r6,[r0,r1,lsl #2]      @  swap
    str r5,[r0,r2,lsl #2] 
    add r3,r3,#1
4:
    mov r1,r8                  @ low
    mov r2,r10                 @ mid
    add r2,r2,r1
    bl circleSort
    mov r3,r0                 @ swaps
    mov r0,r7                 @ table address
    mov r1,r8                 @ low
    mov r2,r10                @ mid
    add r1,r2,r1
    add r1,r1,#1
    mov r2,r9                 @ high
    bl circleSort
    mov r3,r0                 @ swaps
99:
    mov r0,r3                 @ return number swaps
100:
    pop {r1-r10,lr}
    bx lr                                                  @ return 
 
/******************************************************************/
/*      Display table elements                                */ 
/******************************************************************/
/* r0 contains the address of table */
displayTable:
    push {r0-r3,lr}                   @ save registers
    mov r2,r0                         @ table address
    mov r3,#0
1:                                    @ loop display table
    ldr r0,[r2,r3,lsl #2]
    ldr r1,iAdrsZoneConv
    bl conversion10                   @ décimal conversion 
    ldr r0,iAdrsMessResult
    ldr r1,iAdrsZoneConv              @ insert conversion
    bl strInsertAtCharInc
    bl affichageMess                  @ display message
    add r3,#1
    cmp r3,#NBELEMENTS - 1
    ble 1b
    ldr r0,iAdrszCarriageReturn
    bl affichageMess
100:
    pop {r0-r3,lr}
    bx lr
iAdrsZoneConv:           .int sZoneConv
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
.include "../affichage.inc"
Display table before sort.
Value  : 9
Value  : 5
Value  : 12
Value  : 8
Value  : 2
Value  : 12
Value  : 6

Value  : 2
Value  : 5
Value  : 6
Value  : 8
Value  : 9
Value  : 12
Value  : 12

Table sorted.

Arturo

innerCircleSort: function [ar, lo, hi, swaps][
    localSwaps: swaps
    localHi: hi
    localLo: lo
    if localLo = localHi -> return swaps

    high: localHi
    low: localLo
    mid: (localHi - localLo) / 2

    while [localLo < localHi] [
        if ar\[localLo] > ar\[localHi] [
            tmp: ar\[localLo]
            ar\[localLo]: ar\[localHi]
            ar\[localHi]: tmp
            localSwaps: localSwaps + 1
        ]
        localLo: localLo + 1
        localHi: localHi - 1
    ]
    if localLo = localHi [
        if ar\[localLo] > ar\[localHi + 1] [
            tmp: ar\[localLo]
            ar\[localLo]: ar\[localHi + 1]
            ar\[localHi + 1]: tmp
            localSwaps: localSwaps + 1
        ]
    ]

    localSwaps: innerCircleSort ar low low + mid localSwaps
    localSwaps: innerCircleSort ar low + mid + 1 high localSwaps
    return localSwaps
]

circleSort: function [arr][
    result: new arr
    while [not? zero? innerCircleSort result 0 dec size result 0][]
    return result
]

print circleSort [3 1 2 8 5 7 9 4 6]
Output:
1 2 3 4 5 6 7 8 9

AutoHotkey

nums := [6, 7, 8, 9, 2, 5, 3, 4, 1]
while circlesort(nums, 1, nums.Count(), 0)		; 1-based
    continue
for i, v in nums
    output .= v ", "
MsgBox % "[" Trim(output, ", ") "]"
return
 
circlesort(Arr, lo, hi, swaps){
    if (lo = hi)
        return swaps
    high:= hi
    low := lo
    mid := Floor((hi - lo) / 2)
    while (lo < hi) {
        if (Arr[lo] > Arr[hi]){
            tempVal := Arr[lo], Arr[lo] := Arr[hi], Arr[hi] := tempVal
            swaps++
        }
        lo++
        hi--
    }
    if (lo = hi)
        if (Arr[lo] > Arr[hi+1]){
            tempVal := Arr[lo], Arr[lo] := Arr[hi+1], Arr[hi+1] := tempVal
            swaps++
        }
    swaps := circlesort(Arr, low, low+mid, swaps)
    swaps := circlesort(Arr, low+mid+1, high, swaps)
    return swaps
}
Output:
[1, 2, 3, 4, 5, 6, 7, 8, 9]

C

#include <stdio.h>

int circle_sort_inner(int *start, int *end)
{
	int *p, *q, t, swapped;

	if (start == end) return 0;

	// funny "||" on next line is for the center element of odd-lengthed array
	for (swapped = 0, p = start, q = end; p<q || (p==q && ++q); p++, q--)
		if (*p > *q)
			t = *p, *p = *q, *q = t, swapped = 1;

	// q == p-1 at this point
	return swapped | circle_sort_inner(start, q) | circle_sort_inner(p, end);
}

//helper function to show arrays before each call
void circle_sort(int *x, int n)
{
	do {
		int i;
		for (i = 0; i < n; i++) printf("%d ", x[i]);
		putchar('\n');
	} while (circle_sort_inner(x, x + (n - 1)));
}

int main(void)
{
	int x[] = {5, -1, 101, -4, 0, 1, 8, 6, 2, 3};
	circle_sort(x, sizeof(x) / sizeof(*x));

	return 0;
}
Output:
5 -1 101 -4 0 1 8 6 2 3 
-4 -1 0 3 6 1 2 8 5 101 
-4 -1 0 1 2 3 5 6 8 101

C#

using System;
using System.Linq;

namespace CircleSort
{
    internal class Program
    {
        public static int[] CircleSort(int[] array)
        {
            if (array.Length > 0)
                while (CircleSortR(array, 0, array.Length - 1, 0) != 0)
                    continue;
            return array;
        }

        private static int CircleSortR(int[] arr, int lo, int hi, int numSwaps)
        {
            if (lo == hi)
                return numSwaps;

            var high = hi;
            var low = lo;
            var mid = (hi - lo) / 2;

            while (lo < hi)
            {
                if (arr[lo] > arr[hi])
                {
                    (arr[lo], arr[hi]) = (arr[hi], arr[lo]);
                    numSwaps++;
                }
                lo++;
                hi--;
            }

            if (lo == hi && arr[lo] > arr[hi + 1])
            {
                (arr[lo], arr[hi + 1]) = (arr[hi + 1], arr[lo]);
                numSwaps++;
            }

            numSwaps = CircleSortR(arr, low, low + mid, numSwaps);
            numSwaps = CircleSortR(arr, low + mid + 1, high, numSwaps);

            return numSwaps;
        }

        private static void Main(string[] args)
        {
            var sortedArray = CircleSort(new int[] { 6, 7, 8, 9, 2, 5, 3, 4, 1 });
            sortedArray.ToList().ForEach(i => Console.Write(i.ToString() + " "));
            Console.WriteLine();
            var sortedArray2 = CircleSort(new int[] { 2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1 });
            sortedArray2.ToList().ForEach(i => Console.Write(i.ToString() + " "));
            Console.WriteLine();
            var sortedArray3 = CircleSort(new int[] { 2, 3, 3, 5, 5, 1, 1, 7, 7, 6, 6, 4, 4, 0, 0 });
            sortedArray3.ToList().ForEach(i => Console.Write(i.ToString() + " "));
            Console.ReadKey();
        }
    }
}
Output:
1 2 3 4 5 6 7 8 9
-1 0 1 2 3 4 5 6 7 8 11 12 13 14
0 0 1 1 2 3 3 4 4 5 5 6 6 7 7

C++

#include <iostream>

int circlesort(int* arr, int lo, int hi, int swaps) {
    if(lo == hi) {
        return swaps;
    }
    int high = hi;
    int low = lo;
    int mid = (high - low) / 2;
    while(lo < hi) {
        if(arr[lo] > arr[hi]) {
            int temp = arr[lo];
            arr[lo] = arr[hi];
            arr[hi] = temp;
            swaps++;
        }
        lo++;
        hi--;
    }

    if(lo == hi) {
        if(arr[lo] > arr[hi+1]) {
            int temp = arr[lo];
            arr[lo] = arr[hi+1];
            arr[hi+1] = temp;
            swaps++;
        }
    }
    swaps = circlesort(arr, low, low+mid, swaps);
    swaps = circlesort(arr, low+mid+1, high, swaps);
    return swaps;
}

void circlesortDriver(int* arr, int n) {
    do {
        for(int i = 0; i < n; i++) {
            std::cout << arr[i] << ' ';
        }
        std::cout << std::endl;
    } while(circlesort(arr, 0, n-1, 0));
}

int main() {
    int arr[] = { 6, 7, 8, 9, 2, 5, 3, 4, 1 };
    circlesortDriver(arr, sizeof(arr)/sizeof(int));
    return 0;
}

Output:

6 7 8 9 2 5 3 4 1
1 3 4 2 5 6 7 8 9
1 2 3 4 5 6 7 8 9

CoffeeScript

circlesort = (arr, lo, hi, swaps) ->
  if lo == hi
     return (swaps)

  high = hi
  low  = lo
  mid = Math.floor((hi-lo)/2)

  while lo < hi
    if arr[lo] > arr[hi]
       t = arr[lo]
       arr[lo] = arr[hi]
       arr[hi] = t
       swaps++
    lo++
    hi--

  if lo == hi
     if arr[lo] > arr[hi+1]
        t = arr[lo]
        arr[lo] = arr[hi+1]
        arr[hi+1] = t
        swaps++

  swaps = circlesort(arr,low,low+mid,swaps)
  swaps = circlesort(arr,low+mid+1,high,swaps)

  return(swaps)

VA = [2,14,4,6,8,1,3,5,7,9,10,11,0,13,12,-1]

while circlesort(VA,0,VA.length-1,0)
   console.log VA

Output:

console: -1,1,0,3,4,5,8,12,2,9,6,10,7,13,11,14
console: -1,0,1,3,2,5,4,8,6,7,9,12,10,11,13,14
console: -1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14

D

import std.stdio, std.algorithm, std.array, std.traits;

void circlesort(T)(T[] items) if (isMutable!T) {
    uint inner(size_t lo, size_t hi, uint swaps) {
        if (lo == hi)
            return swaps;
        auto high = hi;
        auto low = lo;
        immutable mid = (hi - lo) / 2;

        while (lo < hi) {
            if (items[lo] > items[hi]) {
                swap(items[lo], items[hi]);
                swaps++;
            }
            lo++;
            hi--;
        }

        if (lo == hi && items[lo] > items[hi + 1]) {
            swap(items[lo], items[hi + 1]);
            swaps++;
        }
        swaps = inner(low, low + mid, swaps);
        swaps = inner(low + mid + 1, high, swaps);
        return swaps;
    }

    if (!items.empty)
        while (inner(0, items.length - 1, 0)) {}
}

void main() {
    import std.random, std.conv;

    auto a = [5, -1, 101, -4, 0, 1, 8, 6, 2, 3];
    a.circlesort;
    a.writeln;
    assert(a.isSorted);

    // Fuzzy test.
    int[30] items;
    foreach (immutable _; 0 .. 100_000) {
        auto data = items[0 .. uniform(0, items.length)];
        foreach (ref x; data)
            x = uniform(-items.length.signed * 3, items.length.signed * 3);
        data.circlesort;
        assert(data.isSorted);
    }
}
Output:
[-4, -1, 0, 1, 2, 3, 5, 6, 8, 101]

Delphi

Translation of: Go
program Sorting_Algorithms;

{$APPTYPE CONSOLE}

uses
  System.SysUtils;

function CircleSort(a: TArray<Integer>; lo, hi, swaps: Integer): Integer;
begin
  if lo = hi then
    exit(swaps);

  var high := hi;
  var low := lo;
  var mid := (hi - lo) div 2;

  while lo < hi do
  begin
    if a[lo] > a[hi] then
    begin
      var tmp := a[lo];
      a[lo] := a[hi];
      a[hi] := tmp;
      inc(swaps);
    end;
    inc(lo);
    dec(hi);
  end;

  if lo = hi then
  begin
    if a[lo] > a[hi + 1] then
    begin
      var tmp := a[lo];
      a[lo] := a[hi + 1];
      a[hi + 1] := tmp;
      inc(swaps);
    end;
  end;
  swaps := CircleSort(a, low, low + mid, swaps);
  swaps := CircleSort(a, low + mid + 1, high, swaps);
  result := swaps;
end;

function ToString(a: TArray<Integer>): string;
begin
  Result := '[';
  for var e in a do
    Result := Result + e.ToString + ',';
  Result := Result + ']';
end;

const
  aa: TArray<TArray<Integer>> = [[6, 7, 8, 9, 2, 5, 3, 4, 1], [2, 14, 4, 6, 8, 1,
    3, 5, 7, 11, 0, 13, 12, -1]];

begin
  for var a in aa do
  begin
    write('Original: ');
    write(ToString(a));
    while CircleSort(a, 0, high(a), 0) <> 0 do
      ;
    writeln;
    write('Sorted  : ');
    write(ToString(a));
    writeln(#10#10);
  end;
  readln;
end.

EasyLang

global d[] .
func circsort lo hi swaps .
   if lo = hi
      return swaps
   .
   high = hi
   low = lo
   mid = (hi - lo) div 2
   while lo < hi
      if d[lo] > d[hi]
         swap d[lo] d[hi]
         swaps += 1
      .
      lo += 1
      hi -= 1
   .
   if lo = hi
      if d[lo] > d[hi + 1]
         swap d[lo] d[hi + 1]
         swaps += 1
      .
   .
   swaps = circsort low (low + mid) swaps
   swaps = circsort (low + mid + 1) high swaps
   return swaps
.
d[] = [ -4 -1 1 0 5 -7 -2 4 -6 -3 2 6 3 7 -5 ]
while circsort 1 len d[] 0 > 0
   # 
.
print d[]
Output:
[ -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 ]

Elixir

defmodule Sort do
  def circle_sort(data) do
    List.to_tuple(data)
    |> circle_sort(0, length(data)-1)
    |> Tuple.to_list
  end
  
  defp circle_sort(data, lo, hi) do
    case circle_sort(data, lo, hi, 0) do
      {result, 0} -> result
      {result, _} -> circle_sort(result, lo, hi)
    end
  end
  
  defp circle_sort(data, lo, lo, swaps), do: {data, swaps}
  defp circle_sort(data, lo, hi, swaps) do
    mid = div(lo + hi, 2)
    {data, swaps} = do_circle_sort(data, lo, hi, swaps)
    {data, swaps} = circle_sort(data, lo, mid, swaps)
    circle_sort(data, mid+1, hi, swaps)
  end
  
  def do_circle_sort(data, lo, hi, swaps) when lo>=hi do
    if lo==hi and elem(data, lo) > elem(data, hi+1),
      do:   {swap(data, lo, hi+1), swaps+1},
      else: {data, swaps}
  end
  def do_circle_sort(data, lo, hi, swaps) do
    if elem(data, lo) > elem(data, hi),
      do:   do_circle_sort(swap(data, lo, hi), lo+1, hi-1, swaps+1),
      else: do_circle_sort(data, lo+1, hi-1, swaps)
  end
  
  defp swap(data, i, j) do
    vi = elem(data, i)
    vj = elem(data, j)
    data |> put_elem(i, vj) |> put_elem(j, vi)
  end
end

data = [6, 7, 8, 9, 2, 5, 3, 4, 1]
IO.puts "before sort: #{inspect data}"
IO.puts " after sort: #{inspect Sort.circle_sort(data)}"
Output:
before sort: [6, 7, 8, 9, 2, 5, 3, 4, 1]
 after sort: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Forth

This one features the newest version of the algorithm on Sourceforge.

[UNDEFINED] cell- [IF] : cell- 1 cells - ; [THEN]

defer precedes                         ( addr addr -- flag )
variable (sorted?)                     \ is the array sorted?

: (compare)                            ( a1 a2 -- a1 a2)
  over @ over @ precedes               \ flag if swapped
  if over over over @ over @ swap rot ! swap ! false (sorted?) ! then
;

: (circlesort)                         ( a1 a2 --)
  over over = if drop drop exit then   \ quit if indexes are equal
  over over swap                       \ swap indexes (end begin)
  begin
    over over >                        \ as long as middle isn't passed
  while
    (compare) swap cell- swap cell+    \ check and swap opposite elements
  repeat rot recurse recurse           \ split array and recurse
;

: sort                                 ( a n --)
  1- cells over +                      \ calculate addresses
  begin true (sorted?) ! over over (circlesort) (sorted?) @ until drop drop
;

:noname < ; is precedes
 
10 constant /sample
create sample 5 , -1 , 101 , -4 , 0 , 1 , 8 , 6 , 2 , 3 ,
 
: .sample sample /sample cells bounds do i ? 1 cells +loop ;
 
sample /sample sort .sample

Fortran

!
module circlesort
! I have commented the code that was here and also 'tightened up' various pieces such as how swap detection was done as well
! as fixing an error where the code would exceed array bounds for odd number sized arrays.
! Also, giving some some attribution to the author. - Pete
! This code is a Fortran adaptation of a Forth algorithm laid out by "thebeez" at this URL;
! https://sourceforge.net/p/forth-4th/wiki/Circle%20sort/
!
  implicit none
  logical, private :: csr
  public :: circle_sort
 
contains
 
  recursive logical function csr(a, left, right,n) result(swapped)
    implicit none
    integer, intent(in) :: left, right,n
    integer, intent(inout) :: a(n)
    integer :: lo, hi, mid
    integer :: temp
    logical :: lefthalf,righthalf
!
    swapped = .FALSE.
    if (right <= left) return
    lo = left   !Store the upper and lower bounds of list for
    hi = right  !Recursion later
!
    do while (lo < hi)
!   Swap the pair of elements if hi < lo
       if (a(hi) < a(lo)) then
          swapped = .TRUE.
          temp = a(lo)
          a(lo) = a(hi)
          a(hi) = temp
       endif
       lo = lo + 1
       hi = hi - 1
    end do
!   Special case if array is an odd size (not even)
    if (lo == hi)then
       if(a(hi+1) .lt. a(lo))then
           swapped = .TRUE.
           temp = a(hi+1)
           a(hi+1) = a(lo)
           a(lo) = temp
       endif
    endif
    mid = (left + right) / 2 ! Bisection point
    lefthalf = csr(a, left, mid,n)
    righthalf = csr(a, mid + 1, right,n)
    swapped = swapped .or. lefthalf .or. righthalf
  end function csr
! 
  subroutine circle_sort(a, n)
    use iso_c_binding, only: c_ptr, c_loc
    implicit none
    integer, intent(in) :: n
    integer, target,intent(inout) :: a(n)

    do while ( csr(a, 1, n,n))
! This is the canonical algorithm. However, if you want to
! speed it up, count the iterations and when you have approached
! 0.5*ln(n) iterations, perform a binary insertion sort then exit the loop.
    end do
  end subroutine circle_sort
 
end module circlesort
program sort
  use circlesort
  implicit none
  integer :: a(9)
  data a/6,7,8,9,2,5,3,4,1/
  call circle_sort(a, size(a))
  print *, a
end program sort

FreeBASIC

' version 21-10-2016
' compile with: fbc -s console
' for boundry checks on array's compile with: fbc -s console -exx
' converted pseudo code into FreeBASIC code

' shared variables need to be declared before first use
Dim Shared As Long cs(-7 To 7)

Function circlesort(lo As Long, hi As Long, swaps As ULong) As ULong

    ' array is declared shared 
    ' sort from lower bound to the highter bound
    ' array's can have subscript range from -2147483648 to +2147483647

    If lo = hi Then Return swaps

    Dim As Long high = hi
    Dim As Long low = lo
    Dim As Long mid_ = (hi - lo) \ 2

    While lo < hi
        If cs(lo) > cs(hi) Then
            Swap cs(lo), cs(hi)
            swaps += 1
        End If
        lo += 1
        hi -= 1
    Wend
    If lo = hi Then
        If cs(lo) > cs(hi +1) Then
            Swap cs(lo), cs(hi +1)
            swaps += 1
        End If
    End If
    swaps = circlesort(low          , low + mid_, swaps)
    swaps = circlesort(low + mid_ +1,       high, swaps)

    Return swaps

End Function

' ------=< MAIN >=------

Dim As Long i, a = LBound(cs), b = UBound(cs)

Randomize Timer
For i = a To b : cs(i) = i  : Next
For i = a To b ' little shuffle
    Swap cs(i), cs(Int(Rnd * (b - a +1)) + a)
Next

Print "unsorted ";
For i = a To b : Print Using "####"; cs(i); : Next : Print

' sort the array, loop until sorted
While circlesort(a, b, 0) : Wend

Print "  sorted ";
For i = a To b : Print Using "####"; cs(i); : Next : Print

' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
Output:
unsorted   -4  -1   1   0   5  -7  -2   4  -6  -3   2   6   3   7  -5
  sorted   -7  -6  -5  -4  -3  -2  -1   0   1   2   3   4   5   6   7

Go

package main

import "fmt"

func circleSort(a []int, lo, hi, swaps int) int {
    if lo == hi {
        return swaps
    }
    high, low := hi, lo
    mid := (hi - lo) / 2
    for lo < hi {
        if a[lo] > a[hi] {
            a[lo], a[hi] = a[hi], a[lo]
            swaps++
        }
        lo++
        hi--
    }
    if lo == hi {
        if a[lo] > a[hi+1] {
            a[lo], a[hi+1] = a[hi+1], a[lo]
            swaps++
        }
    }
    swaps = circleSort(a, low, low+mid, swaps)
    swaps = circleSort(a, low+mid+1, high, swaps)
    return swaps
}

func main() {
    aa := [][]int{
        {6, 7, 8, 9, 2, 5, 3, 4, 1},
        {2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1},
    }
    for _, a := range aa {
        fmt.Printf("Original: %v\n", a)
        for circleSort(a, 0, len(a)-1, 0) != 0 {
            // empty block
        }
        fmt.Printf("Sorted  : %v\n\n", a)
    }
}
Output:
Original: [6 7 8 9 2 5 3 4 1]
Sorted  : [1 2 3 4 5 6 7 8 9]

Original: [2 14 4 6 8 1 3 5 7 11 0 13 12 -1]
Sorted  : [-1 0 1 2 3 4 5 6 7 8 11 12 13 14]

Haskell

This code uses the tortoise-and-the-hare technique to split the input list in two and compare the relevant positions.

import Data.Bool (bool)

circleSort :: Ord a => [a] -> [a]
circleSort xs = if swapped then circleSort ks else ks
  where
    (swapped,ks) = go False xs (False,[])
    
    go d []  sks = sks
    go d [x] (s,ks) = (s,x:ks)
    go d xs  (s,ks) =
      let (st,_,ls,rs) = halve d s xs xs
      in go False ls (go True rs (st,ks))
 
    halve d s (y:ys) (_:_:zs) = swap d y (halve d s ys zs)
    halve d s ys     []       = (s,ys,[],[])
    halve d s (y:ys) [_]      = (s,ys,[y | e],[y | not e])
      where e = y <= head ys
 
    swap d x (s,y:ys,ls,rs)
      | bool (<=) (<) d x y = (    d || s,ys,x:ls,y:rs)
      | otherwise           = (not d || s,ys,y:ls,x:rs)
Output:
>>> circleSort [6,7,8,9,2,5,3,4,1]
[1,2,3,4,5,6,7,8,9]

>>> circleSort [2,14,4,6,8,1,3,5,7,11,0,13,12,-1]
[-1,0,1,2,3,4,5,6,7,8,11,12,13,14]

J

Of more parsing and atomic data, or less parsing with large data groups the latter produces faster J programs. Consequently each iteration laminates the original with its reverse. It joins the recursive call to the pairwise minima of the left block to the recursive call of the pairwise maxima of the right block, repeating the operations while the output changes. This is sufficient for power of 2 length data. The pre verb adjusts the data length. And post recovers the original data. This implementation discards the "in place" property described at the sourceforge link.

circle_sort =: post  power_of_2_length@pre    NB. the main sorting verb
power_of_2_length =: even_length_iteration^:_ NB. repeat while the answer changes
even_length_iteration =: (<./ (,&$: |.) >./)@(-:@# ({. ,: |.@}.) ])^:(1<#)
pre =: ,   (-~ >.&.(2&^.))@# # >./            NB. extend data to next power of 2 length
post =: ({.~ #)~                              NB. remove the extra data

Examples:

   show =: [ smoutput

   8 ([: circle_sort&.>@show ;&(?~)) 13  NB. sort lists length 8 and 13
┌───────────────┬────────────────────────────┐
0 6 7 3 4 5 2 13 10 1 4 7 8 5 6 2 0 9 11 12
└───────────────┴────────────────────────────┘
┌───────────────┬────────────────────────────┐
0 1 2 3 4 5 6 70 1 2 3 4 5 6 7 8 9 10 11 12
└───────────────┴────────────────────────────┘
   
   8 ([: circle_sort&.>@show ;&(1 }. 2 # ?~)) 13  NB. data has repetition
┌─────────────────────────────┬──────────────────────────────────────────────────────┐
2 3 3 5 5 1 1 7 7 6 6 4 4 0 012 11 11 4 4 3 3 9 9 7 7 10 10 6 6 2 2 1 1 5 5 8 8 0 0
└─────────────────────────────┴──────────────────────────────────────────────────────┘
┌─────────────────────────────┬──────────────────────────────────────────────────────┐
0 0 1 1 2 3 3 4 4 5 5 6 6 7 70 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12
└─────────────────────────────┴──────────────────────────────────────────────────────┘

Java

import java.util.Arrays;

public class CircleSort {

    public static void main(String[] args) {
        circleSort(new int[]{2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1});
    }

    public static void circleSort(int[] arr) {
        if (arr.length > 0)
            do {
                System.out.println(Arrays.toString(arr));
            } while (circleSortR(arr, 0, arr.length - 1, 0) != 0);
    }

    private static int circleSortR(int[] arr, int lo, int hi, int numSwaps) {
        if (lo == hi)
            return numSwaps;

        int high = hi;
        int low = lo;
        int mid = (hi - lo) / 2;

        while (lo < hi) {
            if (arr[lo] > arr[hi]) {
                swap(arr, lo, hi);
                numSwaps++;
            }
            lo++;
            hi--;
        }

        if (lo == hi && arr[lo] > arr[hi + 1]) {
            swap(arr, lo, hi + 1);
            numSwaps++;
        }

        numSwaps = circleSortR(arr, low, low + mid, numSwaps);
        numSwaps = circleSortR(arr, low + mid + 1, high, numSwaps);

        return numSwaps;
    }

    private static void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }
}
[2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1]
[-1, 1, 0, 4, 3, 8, 12, 2, 7, 6, 11, 5, 13, 14]
[-1, 0, 1, 3, 2, 4, 7, 5, 6, 8, 12, 11, 13, 14]
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14]

jq

Works with: jq version 1.4

With kudos to #Raku.

"circlesort" as defined in this section can be used to sort any JSON array. In case your jq does not have "until" as a builtin, here is its definition:

def until(cond; next): 
     def _until: if cond then . else (next|_until) end;
     _until;
def circlesort:

  def swap(i;j): .[i] as $t | .[i] = .[j] | .[j] = $t;

  # state: [lo, hi, swaps, array]
  def cs:

    # increment lo, decrement hi, and if they are equal, increment hi again
    # i.e. ++hi if --hi == $lo
    def next: # [lo, hi]
      .[0] += 1 | .[1] -= 1 | (if .[0] == .[1] then .[1] += 1 else . end) ;

    .[0] as $start | .[1] as $stop
    | if $start < $stop then
        until(.[0] >= .[1];
	      .[0] as $lo | .[1] as $hi | .[3] as $array
              | if $array[$lo] > $array[$hi] then
		      .[3] = ($array | swap($lo; $hi))
                    | .[2] += 1         # swaps++
                else .
                end
	      | next)
        | .[0] as $lo | .[1] as $hi
        | [$start, $hi, .[2], .[3]] | cs 
	| [$lo, $stop,  .[2], .[3]] | cs
      else .
      end ;

   [0, length-1, 0, .] | cs
   | .[2] as $swaps
   | .[3]
   | if $swaps == 0 then .
      else circlesort
      end ;

Example:

"The quick brown fox jumps over the lazy dog" | split(" ") | circlesort
Output:
$ jq -n -c -f -M circleSort.jq
["The","brown","dog","fox","jumps","lazy","over","quick","the"]

Julia

Works with: Julia version 0.6
function _ciclesort!(arr::Vector, lo::Int, hi::Int, swaps::Int)
    lo == hi && return swaps
    high = hi
    low  = lo
    mid  = (hi - lo) ÷ 2
    while lo < hi
        if arr[lo] > arr[hi]
            arr[lo], arr[hi] = arr[hi], arr[lo]
            swaps += 1
        end
        lo += 1
        hi -= 1
    end
    if lo == hi
        if arr[lo] > arr[hi+1]
            arr[lo], arr[hi+1] = arr[hi+1], arr[lo]
            swaps += 1
        end
    end
    swaps = _ciclesort!(arr, low, low + mid, swaps)
    swaps = _ciclesort!(arr, low + mid + 1, high, swaps)
    return swaps
end

function ciclesort!(arr::Vector)
    while !iszero(_ciclesort!(arr, 1, endof(arr), 0)) end
    return arr
end

v = rand(10)
println("# $v\n -> ", ciclesort!(v))
Output:
# [0.603704, 0.293639, 0.51395, 0.74624, 0.245282, 0.930508, 0.550865, 0.62253, 0.00608894, 0.270426]
 -> [0.00608894, 0.245282, 0.270426, 0.293639, 0.51395, 0.550865, 0.603704, 0.62253, 0.74624, 0.930508]

Kotlin

// version 1.1.0

fun<T: Comparable<T>> circleSort(array: Array<T>, lo: Int, hi: Int, nSwaps: Int): Int {
    if (lo == hi) return nSwaps

    fun swap(array: Array<T>, i: Int, j: Int) {
        val temp  = array[i]
        array[i]  = array[j]
        array[j]  = temp
    }
 
    var high  = hi
    var low   = lo
    val mid   = (hi - lo) / 2
    var swaps = nSwaps
    while (low < high) {
        if (array[low] > array[high]) {
            swap(array, low, high)
            swaps++
        }
        low++
        high--
    }
    if (low == high)
        if (array[low] > array[high + 1]) {
            swap(array, low, high + 1)
            swaps++
        }
    swaps = circleSort(array, lo, lo + mid, swaps)
    swaps = circleSort(array, lo + mid + 1, hi, swaps)
    return swaps
}

fun main(args: Array<String>) {
    val array = arrayOf(6, 7, 8, 9, 2, 5, 3, 4, 1)
    println("Original: ${array.asList()}")
    while (circleSort(array, 0, array.size - 1, 0) != 0) ; // empty statement
    println("Sorted  : ${array.asList()}")
    println()
    val array2 = arrayOf("the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog")
    println("Original: ${array2.asList()}")
    while (circleSort(array2, 0, array2.size - 1, 0) != 0) ;
    println("Sorted  : ${array2.asList()}")    
}
Output:
Original: [6, 7, 8, 9, 2, 5, 3, 4, 1]
Sorted  : [1, 2, 3, 4, 5, 6, 7, 8, 9]

Original: [the, quick, brown, fox, jumps, over, the, lazy, dog]
Sorted  : [brown, dog, fox, jumps, lazy, over, quick, the, the]

Lua

The first argument to the 'inner' function needs to be a reference to the table as Lua cannot use a pointer to the first element's memory address. Conversely the 'outer' function only needs one argument as the size of the table is innately knowable.

-- Perform one iteration of a circle sort
function innerCircle (t, lo, hi, swaps)
  if lo == hi then return swaps end
  local high, low, mid = hi, lo, math.floor((hi - lo) / 2)
  while lo < hi do
    if t[lo] > t[hi] then
      t[lo], t[hi] = t[hi], t[lo]
      swaps = swaps + 1
    end
    lo = lo + 1
    hi = hi - 1
  end
  if lo == hi then
    if t[lo] > t[hi + 1] then
      t[lo], t[hi + 1] = t[hi + 1], t[lo]
      swaps = swaps + 1
    end
  end
  swaps = innerCircle(t, low, low + mid, swaps)
  swaps = innerCircle(t, low + mid + 1, high, swaps)
  return swaps
end

-- Keep sorting the table until an iteration makes no swaps
function circleSort (t)
  while innerCircle(t, 1, #t, 0) > 0 do end
end

-- Main procedure
local array = {6, 7, 8, 9, 2, 5, 3, 4, 1}
circleSort(array)
print(table.concat(array, " "))
Output:
1 2 3 4 5 6 7 8 9

Mathematica /Wolfram Language

ClearAll[CircleSort, NestedCircleSort]
CircleSort[d_List, l_, h_] := 
 Module[{high, low, mid, lo = l, hi = h, data = d},
  If[lo == hi, Return[data]];
  high = hi;
  low = lo;
  mid = Floor[(hi - lo)/2];
  While[lo < hi,
   If[data[[lo]] > data[[hi]],
    data[[{lo, hi}]] //= Reverse;
    ];
   lo++;
   hi--
   ];
  If[lo == hi,
   If[data[[lo]] > data[[hi + 1]],
    data[[{lo, hi + 1}]] //= Reverse;
    ]
   ];
  data = CircleSort[data, low, low + mid];
  data = CircleSort[data, low + mid + 1, high];
  data
 ]
NestedCircleSort[{}] := {}
NestedCircleSort[d_List] := FixedPoint[CircleSort[#, 1, Length[#]] &, d]
NestedCircleSort[Echo@{6, 7, 8, 9, 2, 5, 3, 4, 1}]
NestedCircleSort[Echo@{6, 7, 8, 2, 5, 3, 4, 1}]
NestedCircleSort[Echo@{6, 2, 5, 7, 3, 4, 1}]
NestedCircleSort[Echo@{4, 6, 3, 5, 2, 1}]
NestedCircleSort[Echo@{1, 2, 3, 4, 5}]
NestedCircleSort[Echo@{2, 4, 3, 1}]
NestedCircleSort[Echo@{2, 3, 1}]
NestedCircleSort[Echo@{2, 1}]
NestedCircleSort[Echo@{1}]
NestedCircleSort[Echo@{}]
Output:
>>{6,7,8,9,2,5,3,4,1}
{1,2,3,4,5,6,7,8,9}
>>{6,7,8,2,5,3,4,1}
{1,2,3,4,5,6,7,8}
>>{6,2,5,7,3,4,1}
{1,2,3,4,5,6,7}
>>{4,6,3,5,2,1}
{1,2,3,4,5,6}
>>{1,2,3,4,5}
{1,2,3,4,5}
>>{2,4,3,1}
{1,2,3,4}
>>{2,3,1}
{1,2,3}
>>{2,1}
{1,2}
>>{1}
{1}
>>{}
{}

Nim

proc innerCircleSort[T](a: var openArray[T], lo, hi, swaps: int): int =
  var localSwaps: int = swaps
  var localHi: int = hi
  var localLo: int = lo
  if localLo == localHi:
    return swaps
  
  var `high` = localHi
  var `low` = localLo
  var mid = (localHi - localLo) div 2

  while localLo < localHi:
    if a[localLo] > a[localHi]:
      swap a[localLo], a[localHi]
      inc localSwaps
    inc localLo
    dec localHi
  if localLo == localHi:
    if a[localLo] > a[localHi + 1]:
      swap a[localLo], a[localHi + 1]
      inc localSwaps

  localswaps = a.innerCircleSort(`low`, `low` + mid, localSwaps)
  localSwaps = a.innerCircleSort(`low` + mid + 1, `high`, localSwaps)
  result = localSwaps

proc circleSort[T](a: var openArray[T]) =
  while a.innerCircleSort(0, a.high, 0) != 0:
    discard

var arr = @[@[6, 7, 8, 9, 2, 5, 3, 4, 1], 
            @[2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1]]

for i in 0..arr.high:
  echo "Original: ", $arr[i]
  arr[i].circleSort()
  echo "Sorted: ", $arr[i], if i != arr.high: "\n" else: ""
Output:
Original: @[6, 7, 8, 9, 2, 5, 3, 4, 1]
Sorted: @[1, 2, 3, 4, 5, 6, 7, 8, 9]

Original: @[2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1]
Sorted: @[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14]

Objeck

Translation of: Objeck
class CircleSort {
  function : Main(args : String[]) ~ Nil {
    circleSort([2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1]);
  }
  
  function : circleSort(arr : Int[]) ~ Nil {
    if(arr->Size() > 0) {
      do {
        arr->ToString()->PrintLine();
      } 
      while(CircleSort(arr, 0, arr->Size() - 1, 0) <> 0);
    };
  }
 
  function : CircleSort( arr : Int[], lo : Int, hi : Int, num_swaps : Int) ~ Int {
    if(lo = hi) {
      return num_swaps;
    };


    high := hi;
    low := lo;
    mid := (hi - lo) / 2;
 
    while (lo < hi) {
      if(arr[lo] > arr[hi]) {
        Swap(arr, lo, hi);
        num_swaps++;
      };
      lo++;
      hi--;
    };
     
    if(lo = hi & arr[lo] > arr[hi + 1]) {
      Swap(arr, lo, hi + 1);
      num_swaps++;
    };
 
    num_swaps := CircleSort(arr, low, low + mid, num_swaps);
    num_swaps := CircleSort(arr, low + mid + 1, high, num_swaps);
 
    return num_swaps;
  }
   
  function : Swap(arr : Int[], idx1 : Int, idx2 : Int) ~ Nil {
    tmp := arr[idx1];
    arr[idx1] := arr[idx2];
    arr[idx2] := tmp;
  }
}

Output:

[2,14,4,6,8,1,3,5,7,11,0,13,12,-1]
[-1,1,0,4,3,8,12,2,7,6,11,5,13,14]
[-1,0,1,3,2,4,7,5,6,8,12,11,13,14]
[-1,0,1,2,3,4,5,6,7,8,11,12,13,14]

PARI/GP

This follows the pseudocode pretty closely.

circlesort(v)=
{
	local(v=v); \\ share with cs
	while (cs(1, #v),);
	v;
}
cs(lo, hi)=
{
	if (lo == hi, return (0));
	my(high=hi,low=lo,mid=(hi-lo)\2,swaps);
	while (lo < hi,
		if (v[lo] > v[hi],
			[v[lo],v[hi]]=[v[hi],v[lo]];
			swaps++
		);
		lo++;
		hi--
	);
	if (lo==hi && v[lo] > v[hi+1],
		[v[lo],v[hi+1]]=[v[hi+1],v[lo]];
		swaps++
	);
	swaps + cs(low,low+mid) + cs(low+mid+1,high);
}
print(example=[6,7,8,9,2,5,3,4,1]);
print(circlesort(example));
Output:
[6, 7, 8, 9, 2, 5, 3, 4, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Pascal

{
   source file name on linux is ./p.p

   -*- mode: compilation; default-directory: "/tmp/" -*-
   Compilation started at Sat Mar 11 23:55:25

   a=./p && pc $a.p && $a
   Free Pascal Compiler version 3.0.0+dfsg-8 [2016/09/03] for x86_64
   Copyright (c) 1993-2015 by Florian Klaempfl and others
   Target OS: Linux for x86-64
   Compiling ./p.p
   Linking p
   /usr/bin/ld.bfd: warning: link.res contains output sections; did you forget -T?
   56 lines compiled, 0.0 sec
   1 2 3 4 5 6 7 8 9 

   Compilation finished at Sat Mar 11 23:55:25
}

program sort;

var
   a : array[0..999] of integer;
   i :  integer;

procedure circle_sort(var a : array of integer; left : integer; right : integer);
var swaps : integer;

   procedure csinternal(var a : array of integer; left : integer; right : integer; var swaps : integer);
   var
      lo, hi, mid : integer;
      t           : integer;
   begin
      if left < right then
      begin
	 lo := left;
	 hi := right;
	 while lo < hi do
	 begin
	    if a[hi] < a[lo] then
	    begin
	       t := a[lo]; a[lo] := a[hi]; a[hi] := t;
	       swaps := swaps + 1;
	    end;
	    lo := lo + 1;
	    hi := hi - 1;
	 end;
	 if (lo = hi) and (a[lo+1] < a[lo]) then
	 begin
	    t := a[lo]; a[lo] := a[lo+1]; a[lo+1] := t;
	    swaps := swaps + 1;
	 end;
	 mid := trunc((hi + lo) / 2);
	 csinternal(a, left, mid, swaps);
	 csinternal(a, mid + 1, right, swaps)
      end
   end;

begin;
   swaps := 1;
   while (0 < swaps) do
   begin
      swaps := 0;
      csinternal(a, left, right, swaps);
   end
end;

begin
   {
      generating polynomial coefficients computed in j:  6 7 8 9 2 5 3 4 1x %. ^/~i.9x
      are 6 29999r280 _292519r1120 70219r288 _73271r640 10697r360 _4153r960 667r2016 _139r13440
   }
   a[1]:=6;a[2]:=7;a[3]:=8;a[4]:=9;a[5]:=2;a[6]:=5;a[7]:=3;a[8]:=4;a[9]:=1;
   circle_sort(a,1,9);
   for i := 1 to 9 do write(a[i], ' ');
   writeln();
end.

Perl

Less flexible than the Raku version, as written does only numeric comparisons.

Translation of: Raku
sub circlesort {
    our @x; local *x = shift;
    my($beg,$end) = @_;

    my $swaps = 0;
    if ($beg < $end) {
        my $lo = $beg;
        my $hi = $end;
        while ($lo < $hi) {
            if ($x[$lo] > $x[$hi]) { # 'gt' here for string comparison
                @x[$lo,$hi] = @x[$hi,$lo];
                ++$swaps;
            }
            ++$hi if --$hi == ++$lo
        }
        $swaps += circlesort(\@x, $beg, $hi);
        $swaps += circlesort(\@x, $lo, $end);
    }
    $swaps;
}

my @a = <16 35 -64 -29 46 36 -1 -99 20 100 59 26 76 -78 39 85 -7 -81 25 88>;
while (circlesort(\@a, 0, $#a)) { print join(' ', @a), "\n" }
Output:
-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
-99 -81 -78 -64 -29 -7 -1 16 20 25 26 35 36 39 46 59 76 85 88 100

Phix

with javascript_semantics

sequence array
 
function circle_sort_inner(integer lo, hi, swaps, level=1)
    if lo!=hi then
        integer high := hi,
                low := lo,
                mid := floor((high-low)/2)
        while lo <= hi do
            hi += (lo=hi)
            object alo = array[lo],
                   ahi = array[hi]
            if alo > ahi then
                array[lo] = ahi
                array[hi] = alo
                printf(1,"%V level %d, low %d, high %d\n",{array,level,low,high})
                swaps += 1
            end if
            lo += 1
            hi -= 1
        end while
        swaps = circle_sort_inner(low,low+mid,swaps,level+1)
        swaps = circle_sort_inner(low+mid+1,high,swaps,level+1)
    end if
    return swaps
end function
 
procedure circle_sort()
    printf(1,"%V <== (initial)\n",{array})
    while circle_sort_inner(1, length(array), 0) do ?"loop" end while
    printf(1,"%V <== (sorted)\n",{array})
end procedure
 
array = {5, -1, 101, -4, 0, 1, 8, 6, 2, 3}
--array = {-4,-1,1,0,5,-7,-2,4,-6,-3,2,6,3,7,-5}
--array = {6, 7, 8, 9, 2, 5, 3, 4, 1}
--array = {2,14,4,6,8,1,3,5,7,9,10,11,0,13,12,-1}
--array = {"the","quick","brown","fox","jumps","over","the","lazy","dog"}
--array = {0.603704, 0.293639, 0.513965, 0.746246, 0.245282, 0.930508, 0.550878, 0.622534, 0.006089, 0.270426}
--array = shuffle(deep_copy(array))
circle_sort()
Output:

Shows the full inner workings: call depth and range being considered, after each swap made.

{5,-1,101,-4,0,1,8,6,2,3} <== (initial)
{3,-1,101,-4,0,1,8,6,2,5} level 1, low 1, high 10
{3,-1,6,-4,0,1,8,101,2,5} level 1, low 1, high 10
{0,-1,6,-4,3,1,8,101,2,5} level 2, low 1, high 5
{0,-4,6,-1,3,1,8,101,2,5} level 2, low 1, high 5
{0,-4,-1,6,3,1,8,101,2,5} level 2, low 1, high 5
{-1,-4,0,6,3,1,8,101,2,5} level 3, low 1, high 3
{-4,-1,0,6,3,1,8,101,2,5} level 4, low 1, high 2
{-4,-1,0,3,6,1,8,101,2,5} level 3, low 4, high 5
{-4,-1,0,3,6,1,2,101,8,5} level 2, low 6, high 10
{-4,-1,0,3,6,1,2,8,101,5} level 2, low 6, high 10
{-4,-1,0,3,6,1,2,8,5,101} level 3, low 9, high 10
"loop"
{-4,-1,0,2,6,1,3,8,5,101} level 1, low 1, high 10
{-4,-1,0,2,1,6,3,8,5,101} level 1, low 1, high 10
{-4,-1,0,1,2,6,3,8,5,101} level 3, low 4, high 5
{-4,-1,0,1,2,6,3,5,8,101} level 2, low 6, high 10
{-4,-1,0,1,2,5,3,6,8,101} level 3, low 6, high 8
{-4,-1,0,1,2,3,5,6,8,101} level 4, low 6, high 7
"loop"
{-4,-1,0,1,2,3,5,6,8,101} <== (sorted)

Python

The doctest passes with odd and even length lists. As do the random tests. Please see circle_sort.__doc__ for example use and output.

#python3
#tests: expect no output.
#doctest with  python3 -m doctest thisfile.py
#additional tests:  python3 thisfile.py

def circle_sort_backend(A:list, L:int, R:int)->'sort A in place, returning the number of swaps':
    '''
        >>> L = [3, 2, 8, 28, 2,]
        >>> circle_sort(L)
        3
        >>> print(L)
        [2, 2, 3, 8, 28]
        >>> L = [3, 2, 8, 28,]
        >>> circle_sort(L)
        1
        >>> print(L)
        [2, 3, 8, 28]
    '''
    n = R-L
    if n < 2:
        return 0
    swaps = 0
    m = n//2
    for i in range(m):
        if A[R-(i+1)] < A[L+i]:
            (A[R-(i+1)], A[L+i],) = (A[L+i], A[R-(i+1)],)
            swaps += 1
    if (n & 1) and (A[L+m] < A[L+m-1]):
        (A[L+m-1], A[L+m],) = (A[L+m], A[L+m-1],)
        swaps += 1
    return swaps + circle_sort_backend(A, L, L+m) + circle_sort_backend(A, L+m, R)

def circle_sort(L:list)->'sort A in place, returning the number of swaps':
    swaps = 0
    s = 1
    while s:
        s = circle_sort_backend(L, 0, len(L))
        swaps += s
    return swaps

# more tests!
if __name__ == '__main__':
    from random import shuffle
    for i in range(309):
        L = list(range(i))
        M = L[:]
        shuffle(L)
        N = L[:]
        circle_sort(L)
        if L != M:
            print(len(L))
            print(N)
            print(L)

Quackery

Having read the information on Sourceforge mentioned in the task description, I note that the circle sort is most elegant when sorting an array the length of which is a power of two. Rather than mess with the central element of an odd length array and forego potential parallelisation I chose to pad the array to the nearest power of two with elements that were guaranteed to be in the right place (here, numbers one larger than the largest item in the array and trim it down to size after sorting. Additionally, rather than flagging exchanges, I use an O(n) test to see if a subarray is sorted to avoid unnecessary recursive calls.

The link at the end of the Sourceforge page to a paper on the subject is broken. This link works.

In the demonstration, I sort the characters in a string. In Quackery a string is a particular use of a nest of numbers (dynamic array of bignums). The string is a word from a famously circular novel. It seemed appropriate for such a novel "circle sort".


  [ dup size 2 < iff
      [ drop true ] done
    true swap 
    dup [] != if
      [ behead swap witheach
        [ tuck > if
          [ dip not 
            conclude ] ] ]
    drop ]                    is sorted     ( [ --> b   )

  [ behead swap witheach
      [ 2dup < iff
        nip else drop ] ]     is largest    ( [ --> n   )

  [ dup largest 1+
    over size
    dup 1 
    [ 2dup > while 
      1 << again ]
    nip swap - 
    dup dip [ of join ] 
    swap ]                    is pad        (   [ --> n [ )

  [ swap dup if
      [ negate split drop ] ] is unpad      ( n [ --> [   )

  [ dup size times 
    [ i i^ > not iff
        conclude done
      dup i peek 
      over i^ peek 
      2dup < iff
        [ rot i poke
          i^ poke ]
      else 2drop ] ]          is reorder    (   [ --> [   )
      
  [ pad  
    [ [ dup sorted if done
        reorder
        dup size 2 / split
        recurse swap 
        recurse swap join ]
      dup sorted until ] 
    unpad ]                   is circlesort (   [ --> [   )

  $ "bababadalgharaghtakamminarronnkonnbronntonnerronntuonnthunntrovarrhounawnskawntoohoohoordenenthurnuk"
  dup echo$ cr
  circlesort echo$ cr
Output:
bababadalgharaghtakamminarronnkonnbronntonnerronntuonnthunntrovarrhounawnskawntoohoohoordenenthurnuk
aaaaaaaaaaaabbbbddeeegghhhhhhhikkkklmmnnnnnnnnnnnnnnnnnnnnnoooooooooooooorrrrrrrrrrrstttttttuuuuuvww


Racket

By default this sorts with the numeric < but any other (diadic) function can be used to compare... e.g. string<?.

#lang racket
(define (circle-sort v0 [<? <])
  (define v (vector-copy v0))

  (define (swap-if l r)
    (define v.l (vector-ref v l))
    (define v.r (vector-ref v r))
    (and (<? v.r v.l)
         (begin (vector-set! v l v.r) (vector-set! v r v.l) #t)))

  (define (inr-cs! L R)
    (cond
      [(>= L (- R 1)) #f] ; covers 0 or 1 vectors
      [else
       (define M (quotient (+ L R) 2))
       (define I-moved?
         (for/or ([l (in-range L M)] [r (in-range (- R 1) L -1)])
           (swap-if l r)))
       (define M-moved? (and (odd? (- L R)) (> M 0) (swap-if (- M 1) M)))
       (define L-moved? (inr-cs! L M))
       (define R-moved? (inr-cs! M R))
       (or I-moved? L-moved? R-moved? M-moved?)]))

  (let loop () (when (inr-cs! 0 (vector-length v)) (loop)))
  v)

(define (sort-random-vector)
  (define v (build-vector (+ 2 (random 10)) (λ (i) (random 100))))
  (define v< (circle-sort v <))
  (define sorted? (apply <= (vector->list v<)))
  (printf "   ~.a\n-> ~.a [~a]\n\n" v v< sorted?))

(for ([_ 10]) (sort-random-vector))

(circle-sort '#("table" "chair" "cat" "sponge") string<?)
Output:
   #(36 94 63 51 33)
-> #(33 36 51 63 94) [#t]

   #(73 74 20 20 79)
-> #(20 20 73 74 79) [#t]

   #(83 42)
-> #(42 83) [#t]

   #(53 95 43 33 66 47 1 61 28 96)
-> #(1 28 33 43 47 53 61 66 95 96) [#t]

   #(71 85)
-> #(71 85) [#t]

   #(36 85 50 19 88 17 2 53 21)
-> #(2 17 19 21 36 50 53 85 88) [#t]

   #(5 97 62 21 99 73 17 16 37 28)
-> #(5 16 17 21 28 37 62 73 97 99) [#t]

   #(12 60 89 90 2 95 9 28)
-> #(2 9 12 28 60 89 90 95) [#t]

   #(50 32 30 47 63 74)
-> #(30 32 47 50 63 74) [#t]

   #(63 41)
-> #(41 63) [#t]

'#("cat" "chair" "sponge" "table")

Raku

(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

REXX

This REXX version will work with any numbers that REXX supports, including negative and/or floating point numbers;
it also will work with character strings.

/*REXX program uses a  circle sort algorithm  to sort an array (or list) of numbers.    */
parse arg x                                      /*obtain optional arguments from the CL*/
if x='' | x=","  then x= 6 7 8 9 2 5 3 4 1       /*Not specified?  Then use the default.*/
call make_array  'before sort:'                  /*display the list and make an array.  */
call circleSort       #                          /*invoke the circle sort subroutine.   */
call make_list   ' after sort:'                  /*make a list and display it to console*/
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
circleSort:      do while  .circleSrt(1, arg(1), 0)\==0;     end;                   return
make_array: #= words(x);    do i=1 for #;  @.i= word(x, i);  end;  say arg(1)  x;   return
make_list:  y= @.1;         do j=2 for #-1;  y= y  @.j;      end;  say arg(1)  y;   return
.swap:      parse arg a,b;  parse  value  @.a @.b  with  @.b @.a;  swaps= swaps+1;  return
/*──────────────────────────────────────────────────────────────────────────────────────*/
.circleSrt: procedure expose @.;  parse arg LO,HI,swaps    /*obtain  LO & HI  arguments.*/
            if LO==HI  then return swaps                   /*1 element?  Done with sort.*/
            high= HI;      low= LO;     mid= (HI-LO) % 2   /*assign some indices.       */
                                                           /* [↓]  sort a section of #'s*/
                       do  while LO<HI                     /*sort within a section.     */
                       if @.LO>@.HI  then call .swap LO,HI /*are numbers out of order ? */
                       LO= LO + 1;        HI= HI - 1       /*add to LO;  shrink the HI. */
                       end   /*while*/                     /*just process one section.  */
            _= HI + 1                                      /*point to  HI  plus one.    */
            if LO==HI  &  @.LO>@._  then call .swap LO, _  /*numbers still out of order?*/
            swaps= .circleSrt(low,        low+mid,  swaps) /*sort the   lower  section. */
            swaps= .circleSrt(low+mid+1,  high,     swaps) /*  "   "   higher     "     */
            return swaps                                   /*the section sorting is done*/
output   when using the default input:
before sort:  6 7 8 9 2 5 3 4 1
 after sort:  1 2 3 4 5 6 7 8 9
output   when using the input of:   2 3 3 5 5 1 1 7 7 6 6 4 4 0 0
before sort: 2 3 3 5 5 1 1 7 7 6 6 4 4 0 0
 after sort: 0 0 1 1 2 3 3 4 4 5 5 6 6 7 7
output   when using the input of:   2 3 44 44 5.77 +1 -12345 -3 -3.9 1e7 9
before sort: 2 3 44 44 5.77 +1 -12345 -3 -3.9 1e7 0
 after sort: -12345 -3.9 -3 0 +1 2 3 5.77 44 44 1e7
output   when using the using the input of:   assinine donkey bovine cattle canine dog corvine crow equine horse feline cat hircine goat leporine hare lupine wolf murine rodent piscine fish porcine pig ursine bear vulpine fox
before sort: assinine donkey bovine cattle canine dog corvine crow equine horse feline cat hircine goat leporine hare lupine wolf murine rodent piscine fish porcine pig ursine bear vulpine fox
 after sort: assinine bear bovine canine cat cattle corvine crow dog donkey equine feline fish fox goat hare hircine horse leporine lupine murine pig piscine porcine rodent ursine vulpine wolf

Ring

# Project : Sorting Algorithms/Circle Sort

test = [-4, -1, 1, 0, 5, -7, -2, 4, -6, -3, 2, 6, 3, 7, -5]
while circlesort(1, len(test), 0) end
showarray(test)

func circlesort(lo, hi, swaps)
     if lo = hi
        return swaps
     ok
     high = hi
     low = lo
     mid = floor((hi-lo)/2)
     while lo < hi
           if test[lo] > test[hi]
               temp = test[lo]
               test[lo] = test[hi]
               test[hi] = temp
               swaps = swaps + 1
           ok
           lo = lo + 1
           hi = hi - 1
     end
     if lo = hi
        if test[lo] > test[hi+1] 
           temp = test[lo]
           test[lo] = test[hi+1] 
           test[hi + 1] = temp
           swaps = swaps + 1
        ok
     ok
     swaps = circlesort(low, low+mid, swaps)
     swaps = circlesort(low+mid+1 ,high, swaps)
     return swaps

func showarray(vect)
     see "["
     svect = ""
     for n = 1 to len(vect)
         svect = svect + vect[n] + ", "
     next
     svect = left(svect, len(svect) - 2)
     see svect
     see "]" + nl

Output:

[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]

Ruby

class Array
  def circle_sort!
    while _circle_sort!(0, size-1) > 0
    end
    self
  end
  
  private
  def _circle_sort!(lo, hi, swaps=0)
    return swaps if lo == hi
    low, high = lo, hi
    mid = (lo + hi) / 2
    while lo < hi
      if self[lo] > self[hi]
        self[lo], self[hi] = self[hi], self[lo]
        swaps += 1
      end
      lo += 1
      hi -= 1
    end
    if lo == hi && self[lo] > self[hi+1]
      self[lo], self[hi+1] = self[hi+1], self[lo]
      swaps += 1
    end
    swaps + _circle_sort!(low, mid) + _circle_sort!(mid+1, high)
  end
end

ary = [6, 7, 8, 9, 2, 5, 3, 4, 1]
puts "before sort: #{ary}"
puts " after sort: #{ary.circle_sort!}"
Output:
before sort: [6, 7, 8, 9, 2, 5, 3, 4, 1]
 after sort: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Rust

fn _circle_sort<T: PartialOrd>(a: &mut [T], low: usize, high: usize, swaps: usize) -> usize {
    if low == high {
        return swaps;
    }
    let mut lo = low;
    let mut hi = high;
    let mid = (hi - lo) / 2;
    let mut s = swaps;
    while lo < hi {
        if a[lo] > a[hi] {
            a.swap(lo, hi);
            s += 1;
        }
        lo += 1;
        hi -= 1;
    }
    if lo == hi {
        if a[lo] > a[hi + 1] {
            a.swap(lo, hi + 1);
            s += 1;
        }
    }
    s = _circle_sort(a, low, low + mid, s);
    s = _circle_sort(a, low + mid + 1, high, s);
    return s;
}

fn circle_sort<T: PartialOrd>(a: &mut [T]) {
    let len = a.len();
    loop {
        if _circle_sort(a, 0, len - 1, 0) == 0 {
            break;
        }
    }
}

fn main() {
    let mut v = vec![10, 8, 4, 3, 1, 9, 0, 2, 7, 5, 6];
    println!("before: {:?}", v);
    circle_sort(&mut v);
    println!("after:  {:?}", v);
}
Output:
before: [10, 8, 4, 3, 1, 9, 0, 2, 7, 5, 6]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Scala

object CircleSort extends App {

  def sort(arr: Array[Int]): Array[Int] = {
    def circleSortR(arr: Array[Int], _lo: Int, _hi: Int, _numSwaps: Int): Int = {
      var lo = _lo
      var hi = _hi
      var numSwaps = _numSwaps

      def swap(arr: Array[Int], idx1: Int, idx2: Int): Unit = {
        val tmp = arr(idx1)
        arr(idx1) = arr(idx2)
        arr(idx2) = tmp
      }

      if (lo == hi) return numSwaps
      val (high, low) = (hi, lo)
      val mid = (hi - lo) / 2
      while ( lo < hi) {
        if (arr(lo) > arr(hi)) {
          swap(arr, lo, hi)
          numSwaps += 1
        }
        lo += 1
        hi -= 1
      }
      if (lo == hi && arr(lo) > arr(hi + 1)) {
        swap(arr, lo, hi + 1)
        numSwaps += 1
      }

      circleSortR(arr, low + mid + 1, high, circleSortR(arr, low, low + mid, numSwaps))
    }

    while (circleSortR(arr, 0, arr.length - 1, 0) != 0)()
    arr
  }

  println(sort(Array[Int](2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1)).mkString(", "))

}

Sidef

func circlesort(arr, beg=0, end=arr.end) {
    var swaps = 0
    if (beg < end) {
        var (lo, hi) = (beg, end)
        do {
            if (arr[lo] > arr[hi]) {
                arr.swap(lo, hi)
                ++swaps
            }
            ++hi if (--hi == ++lo)
        } while (lo < hi)
        swaps += circlesort(arr, beg, hi)
        swaps += circlesort(arr, lo, end)
    }
    return swaps
}

var numbers = %n(2 3 3 5 5 1 1 7 7 6 6 4 4 0 0)
do { say numbers } while circlesort(numbers)
 
var strs = ["John", "Kate", "Zerg", "Alice", "Joe", "Jane", "Alice"]
do { say strs } while circlesort(strs)
Output:
[2, 3, 3, 5, 5, 1, 1, 7, 7, 6, 6, 4, 4, 0, 0]
[0, 0, 1, 4, 1, 5, 3, 7, 2, 3, 4, 5, 6, 6, 7]
[0, 0, 1, 1, 2, 3, 3, 4, 4, 5, 5, 7, 6, 6, 7]
[0, 0, 1, 1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7]
["John", "Kate", "Zerg", "Alice", "Joe", "Jane", "Alice"]
["Alice", "Jane", "Alice", "Joe", "John", "Kate", "Zerg"]
["Alice", "Alice", "Jane", "Joe", "John", "Kate", "Zerg"]

Swift

func circleSort<T: Comparable>(_ array: inout [T]) {
    func circSort(low: Int, high: Int, swaps: Int) -> Int {
        if low == high {
            return swaps
        }
        var lo = low
        var hi = high
        let mid = (hi - lo) / 2
        var s = swaps
        while lo < hi {
            if array[lo] > array[hi] {
                array.swapAt(lo, hi)
                s += 1
            }
            lo += 1
            hi -= 1
        }
        if lo == hi {
            if array[lo] > array[hi + 1] {
                array.swapAt(lo, hi + 1)
                s += 1
            }
        }
        s = circSort(low: low, high: low + mid, swaps: s)
        s = circSort(low: low + mid + 1, high: high, swaps: s)
        return s
    }
    while circSort(low: 0, high: array.count - 1, swaps: 0) != 0 {}
}

var array = [10, 8, 4, 3, 1, 9, 0, 2, 7, 5, 6]
print("before: \(array)")
circleSort(&array)
print(" after: \(array)")

var array2 = ["one", "two", "three", "four", "five", "six", "seven", "eight"]
print("before: \(array2)")
circleSort(&array2)
print(" after: \(array2)")
Output:
before: [10, 8, 4, 3, 1, 9, 0, 2, 7, 5, 6]
 after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
before: ["one", "two", "three", "four", "five", "six", "seven", "eight"]
 after: ["eight", "five", "four", "one", "seven", "six", "three", "two"]

uBasic/4tH

This one uses the optimized version featured at Sourceforge.

PRINT "Circle sort:"
  n = FUNC (_InitArray)
  PROC _ShowArray (n)
  PROC _Circlesort (n)
  PROC _ShowArray (n)
PRINT

END

_InnerCircle PARAM (2)
  LOCAL (3)
  c@ = a@
  d@ = b@
  e@ = 0

  IF c@ = d@ THEN RETURN (0)

  DO WHILE c@ < d@
    IF @(c@) > @(d@) THEN PROC _Swap (c@, d@) : e@ = e@ + 1
    c@ = c@ + 1
    d@ = d@ - 1
  LOOP

  e@ = e@ + FUNC (_InnerCircle (a@, d@))
  e@ = e@ + FUNC (_InnerCircle (c@, b@))
RETURN (e@)


_Circlesort PARAM(1)                   ' Circle sort
  DO WHILE FUNC (_InnerCircle (0, a@-1))
  LOOP
RETURN


_Swap PARAM(2)                         ' Swap two array elements
  PUSH @(a@)
  @(a@) = @(b@)
  @(b@) = POP()
RETURN


_InitArray                             ' Init example array
  PUSH 4, 65, 2, -31, 0, 99, 2, 83, 782, 1

  FOR i = 0 TO 9
    @(i) = POP()
  NEXT

RETURN (i)


_ShowArray PARAM (1)                   ' Show array subroutine
  FOR i = 0 TO a@-1
    PRINT @(i),
  NEXT

  PRINT
RETURN

V (Vlang)

Translation of: go
fn circle_sort(mut a []int, l int, h int, s int) int {
    mut hi := h
    mut lo := l
    mut swaps := s
    if lo == hi {
        return swaps
    }
    high, low := hi, lo
    mid := (hi - lo) / 2
    for lo < hi {
        if a[lo] > a[hi] {
            a[lo], a[hi] = a[hi], a[lo]
            swaps++
        }
        lo++
        hi--
    }
    if lo == hi {
        if a[lo] > a[hi+1] {
            a[lo], a[hi+1] = a[hi+1], a[lo]
            swaps++
        }
    }
    swaps = circle_sort(mut a, low, low+mid, swaps)
    swaps = circle_sort(mut a, low+mid+1, high, swaps)
    return swaps
}
 
fn main() {
    aa := [
        [6, 7, 8, 9, 2, 5, 3, 4, 1],
        [2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1],
    ]
    for a1 in aa {
        mut a:=a1.clone()
        println("Original: $a")
        for circle_sort(mut a, 0, a.len-1, 0) != 0 {
            // empty block
        }
        println("Sorted  : $a\n")
    }
}
Output:
Original: [6, 7, 8, 9, 2, 5, 3, 4, 1]
Sorted  : [1, 2, 3, 4, 5, 6, 7, 8, 9]

Original: [2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1]
Sorted  : [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14]

Wren

var circleSort // recursive
circleSort = Fn.new { |a, lo, hi, swaps|
    if (lo == hi) return swaps
    var high = hi
    var low = lo
    var mid = ((hi-lo)/2).floor
    while (lo < hi) {
        if (a[lo] > a[hi]) {
            var t = a[lo]
            a[lo] = a[hi]
            a[hi] = t
            swaps = swaps + 1
        }
        lo = lo + 1
        hi = hi - 1
    }
    if (lo == hi) {
        if (a[lo] > a[hi+1]) {
            var t = a[lo]
            a[lo] = a[hi+1]
            a[hi+1] = t
            swaps = swaps + 1
        }
    }
    swaps = circleSort.call(a, low, low + mid, swaps)
    swaps = circleSort.call(a, low + mid + 1, high, swaps)
    return swaps
}

var array = [ [6, 7, 8, 9, 2, 5, 3, 4, 1], [2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1] ]
for (a in array) {
    System.print("Before: %(a)")
    while (circleSort.call(a, 0, a.count-1, 0) != 0) {}
    System.print("After : %(a)")
    System.print()
}
Output:
Before: [6, 7, 8, 9, 2, 5, 3, 4, 1]
After : [1, 2, 3, 4, 5, 6, 7, 8, 9]

Before: [2, 14, 4, 6, 8, 1, 3, 5, 7, 11, 0, 13, 12, -1]
After : [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14]

XPL0

int  Array;

func CircleSort(Lo, Hi, Swaps);
int  Lo, Hi, Swaps;
int  Low, High, Mid, T;
[if Lo = Hi then return Swaps;
Low:= Lo;
High:= Hi;
Mid:= (Hi-Lo)/2;
while Lo < Hi do
    [if Array(Lo) > Array(Hi) then
        [T:= Array(Lo);  Array(Lo):= Array(Hi);  Array(Hi):= T;
        Swaps:= Swaps+1;
        ];
    Lo:= Lo+1;
    Hi:= Hi-1;
    ];
if Lo = Hi then
    if Array(Lo) > Array(Hi+1) then
        [T:= Array(Lo);  Array(Lo):= Array(Hi+1);  Array(Hi+1):= T;
        Swaps:= Swaps+1;
        ];
Swaps:= CircleSort(Low, Low+Mid, Swaps);
Swaps:= CircleSort(Low+Mid+1, High, Swaps);
return Swaps;
];

int I;
[Array:= [5, -1, 101, -4, 0, 1, 8, 6, 2, 3];
while CircleSort(0, 10-1, 0) # 0 do [];
for I:= 0 to 10-1 do
    [IntOut(0, Array(I));  ChOut(0, ^ )];
]
Output:
-4 -1 0 1 2 3 5 6 8 101 

zkl

fcn circleSort(list){
   csort:=fcn(list,lo,hi,swaps){
      if(lo==hi) return(swaps);
      high,low,mid:=hi,lo,(hi-lo)/2;
      while(lo<hi){
	 if(list[lo]>list[hi]){
	    list.swap(lo,hi);
	    swaps+=1;
	 }
	 lo+=1; hi-=1;
      }
      if(lo==hi)
	 if (list[lo]>list[hi+1]){
	    list.swap(lo,hi+1);
	    swaps+=1;
	 }
      swaps=self.fcn(list,low,low + mid,swaps);
      swaps=self.fcn(list,low + mid + 1,high,swaps);
      return(swaps);
   };
   list.println();
   while(csort(list,0,list.len()-1,0)){ list.println() }
   list
}
circleSort(L(6,7,8,9,2,5,3,4,1));
circleSort(L(5,-1,101,-4,0,1,8,6,2,3));
Output:
L(6,7,8,9,2,5,3,4,1)
L(1,3,4,2,5,6,7,8,9)
L(1,2,3,4,5,6,7,8,9)
L(5,-1,101,-4,0,1,8,6,2,3)
L(-4,-1,0,3,6,1,2,8,5,101)
L(-4,-1,0,1,2,3,5,6,8,101)

ZX Spectrum Basic

A language like ZX BASIC is not the most obvious choice for a routine which depends on local variables and recursion. This program proves that it can be implemented quite efficiently using arrays and global variables. The b and e variables are set up in such a way that they can be used for the first recursive call. The variables for the next recursion are saved in array s() which serves as a stack together with stack pointer p.

The size of the stack is determined by the amount of memory on the ZX Spectrum, which is 64KB (or 216 bytes). Each call requires two array elements. Note the size of a ZX Spectrum floating point number is 5 bytes, so this stack is slightly oversized. The somewhat strange indexing between both recursions is due to an stack pointer adjustment which was optimized away.

This version of Circle sort was based on the optimized version on Sourceforge. It will also show a few asterisks while running, because it will take some time to finish (about two minutes).

   10 DIM a(100): DIM s(32): RANDOMIZE : LET p=1: GO SUB 3000: GO SUB 2000: GO SUB 4000
   20 STOP
 1000 IF b=e THEN RETURN
 1010 LET s(p)=b: LET s(p+1)=e
 1020 IF a(s(p))>a(e) THEN LET t=a(s(p)): LET a(s(p))=a(e): LET a(e)=t: LET c=1
 1030 LET s(p)=s(p)+1: LET e=e-1: IF s(p)<e THEN GO TO 1020
 1040 LET p=p+2: GO SUB 1000: LET b=s(p-2): LET e=s(p-1): GO SUB 1000: LET p=p-2: RETURN
 2000 PRINT "*";: LET b=1: LET e=100: LET c=0: GO SUB 1000: IF c>0 THEN GO TO 2000
 2010 CLS : RETURN
 3000 FOR x=1 TO 100: LET a(x)=RND: NEXT x: RETURN
 4000 FOR x=1 TO 100: PRINT x,a(x): NEXT x: RETURN
Cookies help us deliver our services. By using our services, you agree to our use of cookies.