Odd-Even Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Odd-Even Sort

A highly parallelizable exchange sort: alternates between swapping adjacent odd-indexed pairs and even-indexed pairs, forming the basis for hardware-based sorting networks.

How it works

Odd-Even Sort (originally developed for parallel processors with local interconnections) is a variation of Bubble Sort. Standard Bubble Sort is strictly sequential because each comparison depends on the result of the previous one. Odd-Even Sort separates comparisons into two alternating, independent sweeps:

1. Odd Phase: Compare all adjacent element pairs starting at odd indices: \((A[1], A[2]), (A[3], A[4]), (A[5], A[6]), \dots\). Swap any out-of-order pairs. Because these pairs do not overlap, all comparisons in this phase can run concurrently.
2. Even Phase: Compare all adjacent element pairs starting at even indices: \((A[0], A[1]), (A[2], A[3]), (A[4], A[5]), \dots\). Swap any out-of-order pairs. Again, these comparisons can run concurrently.
3. Repeat: Alternate between Odd and Even phases until a full cycle of both phases occurs without any swaps.

Complexity

Interactive visualization

Pseudocode

procedure oddEvenSort(A):
  n ← length(A)
  sorted ← false
  
  while not sorted:
    sorted ← true
    
    # Odd Phase
    for i from 1 to n - 2 step 2:
      if A[i] > A[i + 1]:
        swap A[i], A[i + 1]
        sorted ← false
        
    # Even Phase
    for i from 0 to n - 2 step 2:
      if A[i] > A[i + 1]:
        swap A[i], A[i + 1]
        sorted ← false

JavaScript implementation

function oddEvenSort(arr) {
  const n = arr.length;
  let sorted = false;
  
  while (!sorted) {
    sorted = true;
    
    // Odd phase
    for (let i = 1; i < n - 1; i += 2) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        sorted = false;
      }
    }
    
    // Even phase
    for (let i = 0; i < n - 1; i += 2) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        sorted = false;
      }
    }
  }
  return arr;
}

Pros and cons

When (not) to use it

• Multi-processor hardware: Ideal for hardware circuits, FPGA routing, and parallel computing clusters.
• Standard software: Avoid for CPU-bound single-thread code; Insertion Sort or Quicksort are much faster.