Circle Sort — VisualAlgorithms Docs

How it works

Compares elements equidistant from both ends, swapping if out of order. Repeats until no swaps needed. Simple and elegant.

Implementation

      
 function circleSort(arr) {
  function circlePass(lo, hi) {
    if (lo >= hi) return false;
    let swapped = false, l = lo, r = hi;
    while (l < r) {
      if (arr[l] > arr[r]) {
        [arr[l], arr[r]] = [arr[r], arr[l]];
        swapped = true;
      }
      l++; r--;
    }
    let mid = (lo + hi) >> 1;
    swapped = circlePass(lo, mid) || swapped;
    swapped = circlePass(mid+1, hi) || swapped;
    return swapped;
  }
  while (circlePass(0, arr.length - 1));
} def circle_sort(arr):
    def circle_pass(lo, hi):
        if lo >= hi: return False
        swapped, l, r = False, lo, hi
        while l < r:
            if arr[l] > arr[r]:
                arr[l], arr[r] = arr[r], arr[l]
                swapped = True
            l += 1; r -= 1
        mid = (lo + hi) >> 1
        s1 = circle_pass(lo, mid)
        s2 = circle_pass(mid+1, hi)
        return swapped or s1 or s2
    while circle_pass(0, len(arr) - 1): pass void circleSort(vector<int>& arr) {
  function<bool(int,int)> cp = [&](int lo, int hi) -> bool {
    if (lo >= hi) return false;
    bool swapped = false;
    int l = lo, r = hi;
    while (l < r) {
      if (arr[l] > arr[r]) { swap(arr[l], arr[r]); swapped = true; }
      l++; r--;
    }
    int mid = (lo+hi) >> 1;
    return cp(lo,mid) | cp(mid+1,hi) | swapped;
  };
  while (cp(0, arr.size()-1));
} void CircleSort(int[] arr) {
  bool CirclePass(int lo, int hi) {
    if (lo >= hi) return false;
    bool swapped = false;
    int l = lo, r = hi;
    while (l < r) {
      if (arr[l] > arr[r]) {
        (arr[l], arr[r]) = (arr[r], arr[l]);
        swapped = true;
      }
      l++; r--;
    }
    int mid = (lo + hi) >> 1;
    return CirclePass(lo,mid) | CirclePass(mid+1,hi) | swapped;
  }
  while (CirclePass(0, arr.Length - 1));
} int circlePass(int arr[], int lo, int hi) {
  if (lo >= hi) return 0;
  int swapped = 0, l = lo, r = hi;
  while (l < r) {
    if (arr[l] > arr[r]) {
      int t = arr[l]; arr[l] = arr[r]; arr[r] = t;
      swapped = 1;
    }
    l++; r--;
  }
  int mid = (lo + hi) >> 1;
  return circlePass(arr,lo,mid) | circlePass(arr,mid+1,hi) | swapped;
}
void circleSort(int arr[], int n) {
  while (circlePass(arr, 0, n - 1));
} 