배처 홀짝 병합 정렬

배처 홀짝 병합 정렬(Batcher odd–even mergesort, Batcher's odd–even mergesort)은 켄 배처가 크기 O(n (log n)²)와 깊이 O((log n)²)의 정렬망을 위해 고안한 구조이다. 여기서 n은 정렬할 항목의 수이다. 점근적으로 최적화된 것은 아니지만 도널드 커누스는 1998년 AKS 네트워크와 관련하여 "n이 지구상의 모든 컴퓨터의 총 메모리 용적을 초과하지만 않는다면 배처의 방식이 훨씬 더 낫다"고 밝혔다.

배처 홀짝 병합 정렬

8개 입력을 받은 홀-짝 병합 정렬망의 시각화
분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도	$O(\log ^{2}(n))$ 병렬 시간
최선 시간복잡도	$O(\log ^{2}(n))$ 병렬 시간
평균 시간복잡도	$O(\log ^{2}(n))$ 병렬 시간
공간복잡도	$O(n\log ^{2}(n))$ 비병렬 시간

그래픽 처리 하드웨어에서 효율적인 정렬을 하는 쉬운 방법으로서 2번째 서적 GPU Gems에 의해 보급되었다.

의사 코드

# note: the input sequence is indexed from 0 to (n-1)
for p = 1, 2, 4, 8, ... # as long as p < n
  for k = p, p/2, p/4, p/8, ... # as long as k >= 1
    for j = mod(k,p) to (n-1-k) with a step size of 2k
      for i = 0 to k-1 with a step size of 1
        if floor((i+j) / (p*2)) == floor((i+j+k) / (p*2))
          compare and sort elements (i+j) and (i+j+k)

외부 링크

• Odd–even mergesort Archived 2019년 12월 22일 - 웨이백 머신 at fh-flensburg.de
• Odd-even mergesort network generator Interactive Batcher's Odd-Even merge-based sorting network generator.