Odd Even Sorting Network

The odd even sorting network is a fixed comparator network derived from odd even transposition sort. It repeatedly applies two phases: compare adjacent pairs starting at even indices, then compare adjacent pairs starting at odd indices.

The schedule is fixed and independent of input values. All comparisons within one phase are independent and can run in parallel.

Problem

Given $n$ elements, sort them in nondecreasing order using a fixed sequence of adjacent compare and exchange operations.

Algorithm

Each round consists of an even phase followed by an odd phase.

odd_even_sorting_network(A):
    for round = 1 to n:
        for i = 0, 2, 4, ...:
            if i + 1 < n and A[i] > A[i + 1]:
                swap A[i], A[i + 1]

        for i = 1, 3, 5, ...:
            if i + 1 < n and A[i] > A[i + 1]:
                swap A[i], A[i + 1]

Each phase can be executed in parallel since the compared pairs do not overlap.

Comparator

Each comparator operates on adjacent elements:

compare_exchange(A, i, i+1):
    if A[i] > A[i+1]:
        swap A[i], A[i+1]

The network consists entirely of adjacent comparators.

Example

For:

After enough rounds, the array becomes sorted.

Complexity

Each round reduces local inversions. Total rounds required is proportional to $n$.

Correctness

Each comparator removes an inversion if two adjacent elements are out of order. Repeating even and odd phases allows elements to move across the array one position per phase. After $n$ rounds, every element can reach its correct position, so all inversions are removed and the array is sorted.

The correctness follows from the same reasoning as odd even transposition sort.

Practical Considerations

• Very simple network structure.
• Works with only adjacent comparisons.
• High total number of comparisons.
• Easy to map onto linear processor arrays or simple hardware.
• Regular memory access pattern.
• Low efficiency compared with $O(n \log n)$ networks.

When to Use

Use the odd even sorting network when:

• simplicity is more important than efficiency
• only adjacent communication is allowed
• implementing a teaching example or hardware model
• small input sizes

Avoid it for large inputs due to quadratic work.

Implementation

func OddEvenSortingNetwork(a []int) {
	n := len(a)

	for round := 0; round < n; round++ {
		for i := 0; i+1 < n; i += 2 {
			if a[i] > a[i+1] {
				a[i], a[i+1] = a[i+1], a[i]
			}
		}

		for i := 1; i+1 < n; i += 2 {
			if a[i] > a[i+1] {
				a[i], a[i+1] = a[i+1], a[i]
			}
		}
	}
}

def odd_even_sorting_network(a):
    n = len(a)

    for _ in range(n):
        for i in range(0, n - 1, 2):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]

        for i in range(1, n - 1, 2):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]