Odd-Even Sort — VisualAlgorithms Docs

How it works

Alternates between odd-indexed and even-indexed passes, comparing and swapping adjacent pairs. Originally designed for parallel processors.
Implementation

      
 function oddEvenSort(arr, stats) {
  const n = arr.length;
  let done = false;
  while (!done) {
    done = true;
    for (let i = 1; i < n - 1; i += 2) {
      compare(i, i + 1);
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swap(i, i + 1);
        done = false;
      }
    }
    for (let i = 0; i < n - 1; i += 2) {
      compare(i, i + 1);
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swap(i, i + 1);
        done = false;
      }
    }
  }
  for (let i = 0; i < n; i++) markSorted(i);
}
 def oddEvenSort(arr, stats):
    done = False
    while not done:
        done = True
        for i in range(1, (n - 1), 2):
            compare(i, (i + 1))
            if (arr[i] > arr[(i + 1)]):
                arr[i], arr[(i + 1)] = arr[(i + 1)], arr[i]
                swap(i, (i + 1))
                done = False
        for i in range(0, (n - 1), 2):
            compare(i, (i + 1))
            if (arr[i] > arr[(i + 1)]):
                arr[i], arr[(i + 1)] = arr[(i + 1)], arr[i]
                swap(i, (i + 1))
                done = False
    for i in range(n):
        markSorted(i)
 #include <vector>
#include <algorithm>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    int done = 0;
    while(!done) {
        done = 1;
        for(int i=1; i<(n - 1); i+=2) {
            compare(i, (i + 1));
            if((arr[i] > arr[(i + 1)])) {
                std::swap(arr[i], arr[(i + 1)]);
                swap(i, (i + 1));
                done = 0;
            }
        }
        for(int i=0; i<(n - 1); i+=2) {
            compare(i, (i + 1));
            if((arr[i] > arr[(i + 1)])) {
                std::swap(arr[i], arr[(i + 1)]);
                swap(i, (i + 1));
                done = 0;
            }
        }
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} public void Sort(int[] arr, int n, dynamic stats) {
    int done = false;
    while(!done) {
        done = true;
        for(int i=1; i<(n - 1); i+=2) {
            compare(i, (i + 1));
            if((arr[i] > arr[(i + 1)])) {
                { int _t = arr[i]; arr[i] = arr[(i + 1)]; arr[(i + 1)] = _t; }
                swap(i, (i + 1));
                done = false;
            }
        }
        for(int i=0; i<(n - 1); i+=2) {
            compare(i, (i + 1));
            if((arr[i] > arr[(i + 1)])) {
                { int _t = arr[i]; arr[i] = arr[(i + 1)]; arr[(i + 1)] = _t; }
                swap(i, (i + 1));
                done = false;
            }
        }
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} #include <stdio.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    int done = 0;
    while(!done) {
        done = 1;
        for(int i=1; i<(n - 1); i+=2) {
            compare(i, (i + 1));
            if((arr[i] > arr[(i + 1)])) {
                { int _t = arr[i]; arr[i] = arr[(i + 1)]; arr[(i + 1)] = _t; }
                swap(i, (i + 1));
                done = 0;
            }
        }
        for(int i=0; i<(n - 1); i+=2) {
            compare(i, (i + 1));
            if((arr[i] > arr[(i + 1)])) {
                { int _t = arr[i]; arr[i] = arr[(i + 1)]; arr[(i + 1)] = _t; }
                swap(i, (i + 1));
                done = 0;
            }
        }
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} 