Odd Even Sort

Odd-even sort, also called brick sort, is a variation of bubble sort that separates comparisons into two alternating phases. One phase compares elements at odd-even index pairs, and the other compares even-odd pairs.

This structure makes the algorithm suitable for parallel execution, since comparisons within each phase do not overlap.

Problem

Given a sequence $A$ of length $n$, reorder it such that

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

Algorithm

Alternate between two passes:

• Odd phase: compare $(1,2), (3,4), (5,6), \dots$
• Even phase: compare $(0,1), (2,3), (4,5), \dots$

Repeat until no swaps occur.

odd_even_sort(A):
    n = length(A)
    sorted = false

    while sorted == false:
        sorted = true

        # even phase
        for i from 0 to n - 2 step 2:
            if A[i] > A[i + 1]:
                swap(A[i], A[i + 1])
                sorted = false

        # odd phase
        for i from 1 to n - 2 step 2:
            if A[i] > A[i + 1]:
                swap(A[i], A[i + 1])
                sorted = false

Example

Let

$$ A = [5, 3, 2, 4, 1] $$

Even phase:

pair	result
(5,3)	[3,5,2,4,1]
(2,4)	[3,5,2,4,1]

Odd phase:

pair	result
(5,2)	[3,2,5,4,1]
(4,1)	[3,2,5,1,4]

Continue until sorted:

$$ [1, 2, 3, 4, 5] $$

Correctness

Each phase performs local corrections on disjoint adjacent pairs. Repeated alternation ensures that all inversions are eventually removed. Since the number of inversions strictly decreases when swaps occur, the algorithm converges to a sorted sequence.

Complexity

case	comparisons	time
best	$n$	$O(n)$
worst	$O(n^2)$	$O(n^2)$
average	$O(n^2)$	$O(n^2)$

Space complexity:

$$ O(1) $$

Properties

• stable
• in-place
• parallelizable per phase

When to Use

This algorithm is useful in parallel or distributed systems where comparisons can be executed simultaneously in each phase. In sequential settings, it offers no advantage over bubble sort.

Implementation

def odd_even_sort(a):
    n = len(a)
    sorted_flag = False

    while not sorted_flag:
        sorted_flag = True

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

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

    return a

func OddEvenSort[T constraints.Ordered](a []T) {
    n := len(a)
    sorted := false

    for !sorted {
        sorted = true

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

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