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

Odd-Even Merge Sort

An optimal parallel sorting network: recursively sorts halves, then performs a structured series of odd-indexed and even-indexed comparison-merges to complete the sort in \(O(\log² n)\) parallel steps.

How it works

Odd-Even Merge Sort, developed by Ken Batcher in 1968, is another foundational parallel sorting network alongside Bitonic Sort. It operates recursively on sizes that are powers of 2. It differs from Bitonic Sort in its merging phase:

1. Recursive Half-Sort: Recursively sort the left half and right half ascending.
2. Odd-Even Merge: Merge the two sorted halves of length \(n\):
   • Even Merge: Stably merge elements at even positions (\(0, 2, 4, \dots\)) using a smaller merge network.
   • Odd Merge: Stably merge elements at odd positions (\(1, 3, 5, \dots\)) using a smaller merge network.
   • Interleave Correction: Interleave the two merged streams. Compare adjacent elements (\(A[1]\) vs. \(A[2]\), \(A[3]\) vs. \(A[4]\), \(\dots\)) and swap them if they are out of order. This completes the full merge in a single parallel comparison step.

Complexity

Interactive visualization

Pseudocode

procedure oddEvenMergeSort(A, lo, n):
  if n > 1:
    m ← n / 2
    oddEvenMergeSort(A, lo, m)
    oddEvenMergeSort(A, lo + m, m)
    oddEvenMerge(A, lo, n, 1)

procedure oddEvenMerge(A, lo, n, r):
  m ← r * 2
  if m < n:
    oddEvenMerge(A, lo, n, m)      # Even index merge
    oddEvenMerge(A, lo + r, n, m)  # Odd index merge
    for i from lo + r to lo + n - r - 1 step m:
      compareSwap(A, i, i + r)
  else:
    compareSwap(A, lo, lo + r)

JavaScript implementation

function oddEvenMergeSort(arr) {
  const n = arr.length;
  
  function compareSwap(i, j) {
    if (i < n && j < n) {
      if (arr[i] > arr[j]) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
  }
  
  function oddEvenMerge(lo, n, r) {
    const m = r * 2;
    if (m < n) {
      oddEvenMerge(lo, n, m);
      oddEvenMerge(lo + r, n, m);
      for (let i = lo + r; i + r < lo + n; i += m) {
        compareSwap(i, i + r);
      }
    } else {
      compareSwap(lo, lo + r);
    }
  }
  
  function oddEvenMergeSortUtil(lo, n) {
    if (n > 1) {
      const m = n / 2;
      oddEvenMergeSortUtil(lo, m);
      oddEvenMergeSortUtil(lo + m, m);
      oddEvenMerge(lo, n, 1);
    }
  }
  
  oddEvenMergeSortUtil(0, n);
  return arr;
}

Pros and cons

When (not) to use it

• Dedicated parallel hardware: Ideal for hardware pipelines, network switches, FPGA architectures, and GPU shaders.
• General programming tasks: Avoid on general-purpose computers; comparison networks have high constant overhead on sequential CPUs.