Parallel Odd Even Sort

Parallel odd even sort is the parallel form of odd even transposition sort. It works like bubble sort, but splits adjacent comparisons into two independent phases. One phase compares pairs starting at even indices, and the other compares pairs starting at odd indices.

Because pairs in the same phase do not overlap, all comparisons in one phase can run at the same time.

Problem

Given an array $A$ of length $n$, sort it in nondecreasing order using repeated parallel adjacent compare and exchange operations.

Algorithm

Each full round has two phases.

parallel_odd_even_sort(A):
    repeat n times:
        parallel for i = 0, 2, 4, ...:
            if i + 1 < n and A[i] > A[i + 1]:
                swap A[i], A[i + 1]

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

The even phase compares:

(A[0], A[1]), (A[2], A[3]), (A[4], A[5]), ...

The odd phase compares:

(A[1], A[2]), (A[3], A[4]), (A[5], A[6]), ...

Example

Start with:

After enough rounds, the array is sorted.

Complexity

Each phase has up to $n/2$ independent comparisons.

Correctness

Each compare and exchange removes one local inversion when two adjacent elements are out of order. Repeating even and odd phases lets every element move across the array through adjacent swaps. After $n$ rounds, any element can travel from one end of the array to the other, so all inversions have been removed and the array is sorted.

Practical Considerations

• The algorithm has poor total work compared with merge sort or quicksort.
• It is easy to parallelize because each phase has independent adjacent pairs.
• It has regular memory access.
• It is useful for teaching parallel synchronization.
• It maps naturally to linear processor arrays and simple sorting networks.

When to Use

Use parallel odd even sort when:

• the input is small
• implementation simplicity matters
• hardware supports synchronized adjacent exchange
• the goal is educational or demonstrative

Avoid it for large production sorting workloads. It performs too many comparisons compared with $O(n \log n)$ sorting algorithms.

Implementation (Go, simplified)

func ParallelOddEvenSort(a []int) {
	n := len(a)
	if n <= 1 {
		return
	}

	for round := 0; round < n; round++ {
		parallelPhase(a, 0)
		parallelPhase(a, 1)
	}
}

func parallelPhase(a []int, start int) {
	done := make(chan struct{})
	count := 0

	for i := start; i+1 < len(a); i += 2 {
		count++
		go func(i int) {
			if a[i] > a[i+1] {
				a[i], a[i+1] = a[i+1], a[i]
			}
			done <- struct{}{}
		}(i)
	}

	for i := 0; i < count; i++ {
		<-done
	}
}