Data Modelling & AI Data Structure & Algorithm

Circle Sort

23 June 2025

0

Circle sort algorithm can be visualized by drawing concentric circles on an array of integers. The elements of the array lying on the same circle diametrically opposite to each other are compared and if found in the wrong order they are swapped. This goes on in a recursive fashion in which the array is divided into sub-arrays on which the above process is repeated until we get pairs of sorted elements which when put together form a sorted array. In short below two steps are repeated while there are swap operations involved in the steps.

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.

It can be better explained by the image below.

Below is the implementation of above algorithm.

CPP

// CPP implementation of Circle Sort
#include<bits/stdc++.h>
using namespace std;
 
// Function to perform circular swaps recursively
// This function returns true if there was a swap
// operation performed.
bool circleSortRec(int a[], int low, int high)
{
    bool swapped = false;
 
    // base case
    if (low == high)
        return false;
 
    // storing the upper and lower bounds
    // of list to be used later in the
    // recursive case
    int lo = low, hi = high;
 
    while (lo < hi)
    {
        // swaps the pair of elements
        // if true
        if (a[lo] > a[hi])
        {
            swap(a[lo], a[hi]);
            swapped = true;
        }
        lo++;
        hi--;
    }
 
    // special case arises only for list
    // of odd size
    if (lo == hi)
        if (a[lo] > a[hi + 1])
        {
            swap(a[low], a[hi+1]);
            swapped = true;
        }
 
    // recursive case to check the
    // traverse lists as sub lists
    int mid = (high - low) / 2;
    bool firstHalf = circleSortRec(a, low, low+mid);
    bool secondHalf = circleSortRec(a, low+mid+1, high);
 
    return swapped || firstHalf || secondHalf;
}
 
// This function mainly calls circleSortRec
void circleSort(int a[], int n)
{
    // Keep calling circleSortRec while
    // there is a swap operation.
    while (circleSortRec(a, 0, n-1))
    {
       ;
    }
}
 
// Driver program
int main()
{
    int a[] = {6, 5, 3, 1, 8, 7, 2, 4};
    int n = sizeof(a)/sizeof(a[0]);
 
    printf("\nUnsorted : ");
    for (int i=0; i<n; i++)
        cout << a[i] << " ";
 
    circleSort(a, n);
 
    printf("\nSorted : ");
    for (int i=0; i<n; i++)
        cout << a[i] << " ";
 
    return 0;
}

Java

// Java implementation of Circle Sort
import java.io.*;
import java.util.*;
 
class GFG {
    // Java function to swap the elements of an array
    public static void swap(int[] arr, int i, int j) {
        int t=arr[i];
        arr[i]=arr[j];
        arr[j]=t;
   }
 
// Function to perform circular swaps recursively
// This function returns true if there was a swap
// operation performed.
public static boolean circleSortRec(int a[], int low, int high)
{
    boolean swapped = false;
   
    // base case
    if (low == high)
        return false;
   
    // storing the upper and lower bounds
    // of list to be used later in the
    // recursive case
    int lo = low, hi = high;
   
    while (lo < hi)
    {
        // swaps the pair of elements
        // if true
        if (a[lo] > a[hi])
        {
            swap(a,lo,hi);
            swapped = true;
        }
        lo++;
        hi--;
    }
   
    // special case arises only for list
    // of odd size
    if (lo == hi)
        if (a[lo] > a[hi + 1])
        {
            swap(a,low,hi+1);
            swapped = true;
        }
   
    // recursive case to check the
    // traverse lists as sub lists
    int mid = (high - low) / 2;
    boolean firstHalf = circleSortRec(a, low, low+mid);
    boolean secondHalf = circleSortRec(a, low+mid+1, high);
   
    return swapped || firstHalf || secondHalf;
}
   
// This function mainly calls circleSortRec
public static void circleSort(int a[], int n)
{
    // Keep calling circleSortRec while
    // there is a swap operation.
    while (circleSortRec(a, 0, n-1))
    {
       ;
    }
}
   
    // Driver code
    public static void main(String[] args)
    {
        int a[] = {6, 5, 3, 1, 8, 7, 2, 4};
        int n = a.length;
   
        System.out.print("Unsorted : ");
        for (int i=0; i<n; i++)
            System.out.print(a[i]+" ");
   
        circleSort(a, n);
   
        System.out.print("\nSorted : ");
        for (int i=0; i<n; i++)
            System.out.print(a[i]+" ");
    }
}
 
// This code is contributed by Pushpesh Raj

C#

// C# implementation of Circle Sort
using System;
 
class GFG 
{
  // function to swap the elements of an array
  public static void swap(int[] arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
  }
 
  // Function to perform circular swaps recursively
  // This function returns true if there was a swap
  // operation performed.
  public static bool circleSortRec(int[] a, int low, int high)
  {
    bool swapped = false;
 
    // base case
    if (low == high)
      return false;
 
    // storing the upper and lower bounds
    // of list to be used later in the
    // recursive case
    int lo = low, hi = high;
 
    while (lo < hi)
    {
      // swaps the pair of elements
      // if true
      if (a[lo] > a[hi])
      {
        swap(a,lo,hi);
        swapped = true;
      }
      lo++;
      hi--;
    }
 
    // special case arises only for list
    // of odd size
    if (lo == hi)
      if (a[lo] > a[hi + 1])
      {
        swap(a,low,hi+1);
        swapped = true;
      }
 
    // recursive case to check the
    // traverse lists as sub lists
    int mid = (high - low) / 2;
    bool firstHalf = circleSortRec(a, low, low+mid);
    bool secondHalf = circleSortRec(a, low+mid+1, high);
 
    return swapped || firstHalf || secondHalf;
  }
 
  // This function mainly calls circleSortRec
  public static void circleSort(int[] a, int n)
  {
    // Keep calling circleSortRec while
    // there is a swap operation.
    while (circleSortRec(a, 0, n-1))
    {
      ;
    }
  }
 
  // Driver code
  static public void Main ()
  {
    int[] a = {6, 5, 3, 1, 8, 7, 2, 4};
    int n = a.Length;
 
    Console.Write("Unsorted : ");
    for (int i = 0; i < n; i++)
      Console.Write(a[i]+" ");
 
    circleSort(a, n);
 
    Console.Write("\nSorted : ");
    for (int i = 0; i < n; i++)
      Console.Write(a[i]+" ");
  }
}
 
// This code is contributed by Aman Kumar.

Python3

# Python implementation of Circle Sort
import sys
 
# Function to perform circular swaps recursively
# This function returns true if there was a swap
# operation performed.
def circleSortRec(a, low, high):
    swapped = False
 
    # base case
    if (low == high):
        return False
 
    # storing the upper and lower bounds
    # of list to be used later in the
    # recursive case
    lo, hi = low, high
 
    while (lo < hi):
        # swaps the pair of elements
        # if true
        if (a[lo] > a[hi]):
            a[lo], a[hi] = a[hi], a[lo]
            swapped = True
        lo += 1
        hi -= 1
 
    # special case arises only for list
    # of odd size
    if (lo == hi):
        if (a[lo] > a[hi + 1]):
            a[low], a[hi+1] = a[hi+1], a[low]
            swapped = True
 
    # recursive case to check the
    # traverse lists as sub lists
    mid = (high - low) // 2
    firstHalf = circleSortRec(a, low, low+mid)
    secondHalf = circleSortRec(a, low+mid+1, high)
 
    return swapped or firstHalf or secondHalf
 
# This function mainly calls circleSortRec
def circleSort(a, n):
    # Keep calling circleSortRec while
    # there is a swap operation.
    while (circleSortRec(a, 0, n-1)):
        pass
 
# Driver program
a = [6, 5, 3, 1, 8, 7, 2, 4]
n = len(a)
 
print("\nUnsorted : ", end="")
for i in range(n):
    print(a[i], end=" ")
 
circleSort(a, n)
 
print("\nSorted : ", end="")
for i in range(n):
    print(a[i], end=" ")

Javascript

// Function to perform circular swaps recursively
// This function returns true if there was a swap
// operation performed.
function circleSortRec(a, low, high) {
let swapped = false;
 
// base case
if (low === high) {
return false;
}
 
// storing the upper and lower bounds
// of list to be used later in the
// recursive case
let lo = low, hi = high;
 
while (lo < hi) {
// swaps the pair of elements
// if true
if (a[lo] > a[hi]) {
[a[lo], a[hi]] = [a[hi], a[lo]];
swapped = true;
}
lo++;
hi--;
}
 
// special case arises only for list
// of odd size
if (lo === hi) {
if (a[lo] > a[hi + 1]) {
[a[low], a[hi+1]] = [a[hi+1], a[low]];
swapped = true;
}
}
 
// recursive case to check the
// traverse lists as sub lists
let mid = Math.floor((high - low) / 2);
let firstHalf = circleSortRec(a, low, low + mid);
let secondHalf = circleSortRec(a, low + mid + 1, high);
 
return swapped || firstHalf || secondHalf;
}
 
// This function mainly calls circleSortRec
function circleSort(a, n) {
 
// Keep calling circleSortRec while
// there is a swap operation.
while (circleSortRec(a, 0, n-1)) {
 
// Do nothing
}
}
 
// Driver program
let a = [6, 5, 3, 1, 8, 7, 2, 4];
let n = a.length;
 
console.log("\nUnsorted : ", a.join(" "));
 
circleSort(a, n);
 
console.log("\nSorted : ", a.join(" "));

Output :

Unsorted : 6 5 3 1 8 7 2 4 
Sorted : 1 2 3 4 5 6 7 8

Time Complexity: O(N²)
Auxiliary Space: O(1)

References : SourceForge This article is contributed by Palash Nigam . If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Circle Sort

CPP

Java

C#

Python3

Javascript

Is MCP Already Outdated? The Real Reason Anthropic Shipped Skills—and How to Pair Them with Milvus

Unlocking 8× Milvus Performance with Cloudian HyperStore and NVIDIA RDMA for S3 Storage

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

LEAVE A REPLY Cancel reply

Most Popular

T-Mobile will now start charging for a perk that used to be free

Spotify now lets you transfer playlists from other services

Google’s Nano Banana Pro lands in the Gemini app for all

Perplexity’s Atlas competitor debuts on Android

EDITOR PICKS

T-Mobile will now start charging for a perk that used to be free

Spotify now lets you transfer playlists from other services

Google’s Nano Banana Pro lands in the Gemini app for all

POPULAR POSTS

T-Mobile will now start charging for a perk that used to be free

Spotify now lets you transfer playlists from other services

Google’s Nano Banana Pro lands in the Gemini app for all

POPULAR CATEGORY

ABOUT US

FOLLOW US