Circle Sort

Circle sort can be done by drawing concentric circle on an array of integers. In the Circle sort the first element compared with the last element and the second element compared with the second last element and so on. If the elements are found in the wrong order, then they are swapped. This process goes on a recursively in which the array is divided into sub-arrays and repeat the above process until we get pairs of sorted elements.

Example

Let's arrange the numbers in ascending order using circle sort.

• Unsorted List

• Iteration 1

compare, swap and divide the array

• Iteration 2

• Iteration 3

• Iteration 4

Algorithm

1.Compare the first element with the last element and second element with the second last element and so on.
2.If the element are not in the correct order swap.
3.Split the array in two parts and recurse until there is only one single element in the array.

Pseudocode

function boolean circleSort( a : array of items, int low, int high )

    boolean swap = false 
    
    int l = low, h = high
   
    while ( l < h )
      		
        if ( a[l] > a[h] )
            swap ( a[l], a[h] )
            swap = true
        end if

        l++
        h--
    
    end while
   
    if ( l == hi )
        if( a[l] > a[h + 1] )
            swap ( a[l], a[h + 1] )
            swap = true
        end if 
    end if
     
    int mid = ( high - low ) / 2
    bool firstArray = circleSort( a, low, low + mid )
    bool secondArray = circleSort( a, low + mid + 1, high )
   
    return swap || firstArray || secondArray
    
end function

Time complexity

Best Case complexity = O(n log n)
Worst case complexity = O(n log n log n)