Pairwise Sorting Network

Pairwise sorting network is a comparison sorting algorithm defined as a fixed network of compare and swap operations. It performs sorting through a sequence of pairwise comparisons arranged in stages.

Unlike adaptive algorithms, its structure does not depend on input values. This makes it suitable for parallel execution and hardware implementation.

Problem

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

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

Idea

The algorithm operates in rounds. In each round, pairs of elements at specific positions are compared and swapped if needed.

The network is designed so that after all rounds, all inversions are eliminated.

Typical stages include:

• compare adjacent pairs
• compare elements at increasing distances
• refine ordering through repeated passes

Algorithm

pairwise_sort(A):
    for gap = 1, 2, 4, ..., n/2:
        for i from 0 to n - gap - 1:
            if (i // gap) % 2 == 0:
                compare_and_swap(A, i, i + gap)

Each stage compares elements at distance equal to the current gap.

Example

Let:

$$ A = [5, 2, 8, 1] $$

Stages:

1. gap = 1 compare (0,1), (2,3) → [2,5,1,8]

2. gap = 2 compare (0,2), (1,3) → [1,5,2,8]

3. gap = 1 compare (0,1), (2,3) → [1,2,5,8]

Final result:

$$ [1,2,5,8] $$

Correctness

Each stage reduces the number of inversions by enforcing ordering constraints between pairs. The sequence of stages is designed so that all pairs of elements that could be out of order are eventually compared. After all stages, no inversions remain, so the array is sorted.

Complexity

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

Properties

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

Notes

Pairwise sorting networks are useful in hardware and SIMD implementations where predictable execution is required. They avoid branching and allow efficient parallelization.

They are generally slower than comparison based adaptive sorts on CPUs due to higher asymptotic cost.

Implementation

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

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

    gap = 1
    while gap < n:
        for i in range(n - gap):
            if (i // gap) % 2 == 0:
                compare_and_swap(i, i + gap)
        gap *= 2

    return a

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

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

	for gap := 1; gap < n; gap *= 2 {
		for i := 0; i < n-gap; i++ {
			if (i/gap)%2 == 0 {
				compareAndSwap(i, i+gap)
			}
		}
	}
}