Home/Sorting/Odd-even sort
Search algorithmsCTRL K

Odd-even sort

· alternating independent pairs
/sorting/odd-even-sort
COMPARISONS
0
so far
SWAPS
0
one per inversion fixed
ROUNDS
0
odd phase plus even phase
PHASE
—
which pairs are compared
PAIRS
12
compared per phase, all at once
comparingswappedin place
n = 24 · seed 7 · 277 steps
step 0 / 276
Size24
odd_even_sort.ts
1
function oddEvenSort(array: number[]) {
2
  let sorted = false;
3
  while (!sorted) {
4
    sorted = true;
5
    for (let i = 1; i + 1 < array.length; i += 2) {
6
      if (array[i] > array[i + 1]) { swap(array, i, i + 1); sorted = false; }
7
    }
8
    for (let i = 0; i + 1 < array.length; i += 2) {
9
      if (array[i] > array[i + 1]) { swap(array, i, i + 1); sorted = false; }
10
    }
11
  }
12
}
CURRENT STEP
line 2

Start. Each round has two phases: odd pairs (1-2, 3-4, …) then even pairs (0-1, 2-3, …); every pair in a phase is independent.

// how it works

Understanding Odd-even sort

odd-even sort · bubble sort rearranged so a whole phase can run at once
01

The idea

Odd-even transposition sort compares the pairs (1, 2), (3, 4), (5, 6), … in one phase and the pairs (0, 1), (2, 3), (4, 5), … in the next, swapping each pair that is out of order. No two pairs in a phase share an element, so every comparison of a phase can happen at the same time.

On one processor it is just bubble sort with a stranger order, and it does the same O(n²) work. On n/2 processors, one per pair, each phase costs one step and the whole sort finishes in n rounds: that is what it was designed for, and why it appears in sorting networks and GPU code.

02

The four stages

1
odd phasepairs (1, 2), (3, 4), …
2
compareeach pair, independently
3
swapthe pairs out of order
4
even phasepairs (0, 1), (2, 3), …; stop when a round swaps nothing
03

Complexity

best
O(n)already sorted: one round
average
O(n²)sequential: the same as bubble sort
worst
O(n)parallel, with n/2 comparators: n rounds
space
O(1)in place
04

Versus its siblings

ROUNDS AT N = 1 000 · PARALLEL
odd-even
1,000
bitonic
55
batcher merge
55
bubble (serial)
999,000
a round is one parallel step; bubble sort cannot parallelise its passes
05

Pseudocode

ODDEVENSORT(array)
  repeat until a round swaps nothing
    odd phase: for every pair (1, 2), (3, 4), … in parallel: swap if out of order
    even phase: for every pair (0, 1), (2, 3), … in parallel: swap if out of order
06

When to use

Hardware and GPUs: a fixed sorting network with n/2 comparators per phase.
Systolic arrays and mesh-connected processors, where each element only talks to its neighbours.
07

Pitfalls

Sequentially it has no advantage at all; it exists for parallel hardware.
Stopping early needs a global 'no swap' flag, which itself costs a reduction step in parallel.
Bitonic and Batcher networks need O(log² n) rounds instead of n; use them when depth matters.
08

History

Nico Habermann described the parallel neighbour sort in 1972 for arrays of processors. It is the simplest sorting network, and the proof that n rounds always suffice, by the 0-1 principle, is a classic exercise in parallel algorithms courses.

Back to Sorting