Odd Even Merge Sort

Odd even merge sort is a comparison sorting algorithm designed as a sorting network. It uses a fixed pattern of compare and swap operations, independent of the input values.

It is closely related to bitonic sort but uses a different merging strategy. It is especially useful in parallel hardware and SIMD execution environments.

Problem

Given an array $A$ of length $n$, reorder it such that:

$$ A[0] \le A[1] \le \dots \le A[n-1] $$

The algorithm is simplest when $n$ is a power of two.

Idea

The algorithm consists of:

step	purpose
recursive sort	sort halves independently
odd even merge	merge sorted halves using structured comparisons

The merge step works by separating elements into odd and even indexed subsequences and merging them recursively.

Algorithm

odd_even_merge_sort(A, lo, n):
    if n <= 1:
        return

    k = n / 2

    odd_even_merge_sort(A, lo, k)
    odd_even_merge_sort(A, lo + k, k)

    odd_even_merge(A, lo, n, 1)

odd_even_merge(A, lo, n, step):
    if step < n:
        odd_even_merge(A, lo, n, step * 2)
        odd_even_merge(A, lo + step, n, step * 2)

        for i from lo + step to lo + n - step - 1 step 2*step:
            compare_and_swap(A, i, i + step)

Example

Let:

$$ A = [5, 3, 8, 1, 7, 2, 6, 4] $$

Recursive sorting produces two sorted halves:

• [1, 3, 5, 8]
• [2, 4, 6, 7]

Odd even merge performs structured comparisons:

• compare adjacent elements across halves
• refine order through recursive merging

Final result:

$$ [1, 2, 3, 4, 5, 6, 7, 8] $$

Correctness

The recursive sorting ensures both halves are sorted. The odd even merge step interleaves comparisons between elements at specific positions. These comparisons gradually enforce the correct ordering constraints across the entire sequence. By recursion on step size, all inversions are eliminated, resulting in a sorted sequence.

Complexity

metric	value
time sequential	$O(n \log^2 n)$
parallel depth	$O(\log^2 n)$
comparisons	fixed pattern

Properties

property	value
stable	no
in-place	yes
data independent	yes
parallel friendly	yes
hardware suitability	high

Notes

Odd even merge sort is used in sorting networks where predictable execution is required. It avoids data dependent branching, which is important for parallel processors and GPUs.

Although slower than $O(n \log n)$ algorithms in sequential settings, it performs well when executed in parallel.

Implementation

def odd_even_merge_sort(a):
    def compare_and_swap(i, j):
        if a[i] > a[j]:
            a[i], a[j] = a[j], a[i]

    def merge(lo, n, step):
        if step < n:
            merge(lo, n, step * 2)
            merge(lo + step, n, step * 2)

            for i in range(lo + step, lo + n - step, 2 * step):
                compare_and_swap(i, i + step)

    def sort(lo, n):
        if n <= 1:
            return

        k = n // 2
        sort(lo, k)
        sort(lo + k, k)
        merge(lo, n, 1)

    sort(0, len(a))
    return a

func OddEvenMergeSort(a []int) {
	var compareAndSwap func(int, int)
	compareAndSwap = func(i, j int) {
		if a[i] > a[j] {
			a[i], a[j] = a[j], a[i]
		}
	}

	var merge func(int, int, int)
	merge = func(lo, n, step int) {
		if step < n {
			merge(lo, n, step*2)
			merge(lo+step, n, step*2)

			for i := lo + step; i < lo+n-step; i += 2 * step {
				compareAndSwap(i, i+step)
			}
		}
	}

	var sort func(int, int)
	sort = func(lo, n int) {
		if n <= 1 {
			return
		}

		k := n / 2
		sort(lo, k)
		sort(lo+k, k)
		merge(lo, n, 1)
	}

	sort(0, len(a))
}