# Odd Even Merge Sort

# 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

```text id="p4k9qx"
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)
```

```text id="v2m8tn"
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

```python id="k7s2xp"
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
```

```go id="q3v9tp"
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))
}
```